370
个编辑
更改
跳到导航
跳到搜索
第1,369行：
第1,369行： − + − 递归算法的时间效率 + − 递归算法的'''<font color="#ff8000"> 时间效率time efficiency </font>'''可以用大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。 − + − 捷径规则（主定理）+ + + 第1,382行：
第1,383行： + + − 那么时间复杂度的大O为： − 如果<Math>f(n) = O(n ^ { \log_b a - \epsilon})</Math>，对于一些常数<Math>\epsilon > 0</Math>，那么 <Math>T(n) = \Theta(n ^ {\log_b a})</Math> + − 如果 <Math>f(n) = \Theta(n ^ { \log_b a })</Math>, 那么 <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>+ − + + + − 其中，a代表每一级递归的递归调用次数，b代表下一级递归的输入小多少系数（即把问题分成多少块），f（n）代表函数在每一级递归中独立于任何递归（如分割、重新组合）的工作。+
→Time-efficiency of recursive algorithms
[[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>
* 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>
那么时间复杂度的大O为：
如果 <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) = O(n ^ { \log_b a - \epsilon})</Math>，对于一些常数<Math>\epsilon > 0</Math>，那么 <Math>T(n) = \Theta(n ^ {\log_b a})</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>
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.
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.
其中，{{mvar|a}}代表每一级递归的递归调用次数，{{mvar|b}}代表下一级递归的输入会小多少（即把问题分成多少块）， {{math|''f'' (''n'')}} 代表函数在每一级递归中独立于任何递归（如分割、重新组合）的工作。
==See also==
==See also==