2,367
个编辑
更改
跳到导航
跳到搜索
第1,116行：
第1,116行： − The [[time complexity|time efficiency]] of recursive algorithms can be expressed in a [[recurrence relation]] of [[Big O notation]]. They can (usually) then be simplified into a single Big-O term. − − {{Main|Master theorem (analysis of algorithms)}} − If the time-complexity of the function is in the form − − − − Then the Big O of the time-complexity is thus: − − * If <Math>f(n) = O(n ^ { \log_b a - \epsilon})</Math> for some constant <Math>\epsilon > 0</Math>, then <Math>T(n) = \Theta(n ^ {\log_b a})</Math> − * If <Math>f(n) = \Theta(n ^ { \log_b a })</Math>, then <Math>T(n) = \Theta(n ^ { \log_b a} \log n)</Math> − * If <Math>f(n) = \Omega(n ^ { \log_b a + \epsilon})</Math> for some constant <Math>\epsilon > 0</Math>, and if <Math>a \cdot f(n / b) \leq c \cdot f(n)</Math> for some constant {{mvar|c}} < 1 and all sufficiently large {{mvar|n}}, then <Math>T(n) = \Theta(f(n))</Math> 第1,143行：
第1,131行： − − where {{mvar|a}} represents the number of recursive calls at each level of recursion, {{mvar|b}} represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and {{math|''f'' (''n'')}} represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion.
→递归算法的时间效率
==递归算法的时间效率==
==递归算法的时间效率==
递归算法的'''<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'')}} 代表函数在每一级递归中独立于任何递归（如分割、重新组合）的工作。