2,443
个编辑
更改
→递归算法的时间效率
==递归算法的时间效率==
==递归算法的时间效率==
递归算法的'''<font color="#ff8000"> 时间效率 time efficiency </font>'''可以用关于大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。
递归算法的'''<font color="#ff8000"> 时间效率 time efficiency </font>'''可以用关于大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。
===捷径规则（主定理）===
===捷径规则（主定理）===
如果函数的时间复杂度为以下形式：
如果函数的时间复杂度为以下形式：
<Math>T(n) = a \cdot T(n / b) + f(n)</Math>
<Math>T(n) = a \cdot T(n / b) + f(n)</Math>
* 如果 <Math>f(n) = \Theta(n ^ { \log_b a })</Math>, 那么 <Math>T(n) = \Theta(n ^ { \log_b a} \log n)</Math>
* 如果 <Math>f(n) = \Theta(n ^ { \log_b a })</Math>, 那么 <Math>T(n) = \Theta(n ^ { \log_b a} \log n)</Math>
* 如果 <Math>f(n) = \Omega(n ^ { \log_b a + \epsilon})</Math> 对于一些常数 <Math>\epsilon > 0</Math>, 且如果<Math>a \cdot f(n / b) \leq c \cdot f(n)</Math> 对于一些常数{{mvar|c}} < 1 和 所有足够大的 {{mvar|n}}, 则 <Math>T(n) = \Theta(f(n))</Math>
* 如果 <Math>f(n) = \Omega(n ^ { \log_b a + \epsilon})</Math> 对于一些常数 <Math>\epsilon > 0</Math>, 且如果<Math>a \cdot f(n / b) \leq c \cdot f(n)</Math> 对于一些常数{{mvar|c}} < 1 和 所有足够大的 {{mvar|n}}, 则 <Math>T(n) = \Theta(f(n))</Math>
其中，{{mvar|a}}代表每一级递归的递归调用次数，{{mvar|b}}代表下一级递归的输入会小多少（即把问题分成多少块）， {{math|''f'' (''n'')}} 代表函数在每一级递归中独立于任何递归（如分割、重新组合）的工作。
其中，{{mvar|a}}代表每一级递归的递归调用次数，{{mvar|b}}代表下一级递归的输入会小多少（即把问题分成多少块）， {{math|''f'' (''n'')}} 代表函数在每一级递归中独立于任何递归（如分割、重新组合）的工作。