更改

[[Image:Recursive2.svg|350px]]

[[Image:Recursive2.svg|350px]]

==Time-efficiency of recursive algorithms==

==递归算法的时间效率==

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.

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.

===Shortcut rule (master theorem)===

递归算法的'''<font color="#ff8000"> 时间效率 time efficiency </font>'''可以用关于大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。

 

===捷径规则（主定理）===

 

{{Main|Master theorem (analysis of algorithms)}}

{{Main|Master theorem (analysis of algorithms)}}

If the time-complexity of the function is in the form

If the time-complexity of the function is in the form

<Math>T(n) = a \cdot T(n / b) + f(n)</Math>

<Math>T(n) = a \cdot T(n / b) + f(n)</Math>

Then the Big O of the time-complexity is thus:

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) = 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) = \Theta(n ^ { \log_b a })</Math>, then <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}} &lt; 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}} &lt; 1 和 所有足够大的 {{mvar|n}}, 则 <Math>T(n) = \Theta(f(n))</Math>

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''&thinsp;(''n'')}} represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion.

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''&thinsp;(''n'')}} represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion.

==See also==

==See also==