更改

删除15字节 、 2020年12月12日 (六) 23:13
第1,369行: 第1,369行:  
[[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.
递归算法的'''<font color="#ff8000"> 时间效率time efficiency </font>'''可以用大O符号的递归关系来表示。然后,它们(通常)可以被简化为一个大O项。
     −
===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
第1,382行: 第1,383行:     
<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:
   −
那么时间复杂度的大O为:
   
* 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>
如果<Math>f(n) = O(n ^ { \log_b a - \epsilon})</Math>,对于一些常数<Math>\epsilon > 0</Math>,那么 <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}} &lt; 1 and all sufficiently large {{mvar|n}}, then <Math>T(n) = \Theta(f(n))</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}} &lt; 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}} &lt; 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}} &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.
   −
其中,a代表每一级递归的递归调用次数,b代表下一级递归的输入小多少系数(即把问题分成多少块),f(n)代表函数在每一级递归中独立于任何递归(如分割、重新组合)的工作。
+
其中,{{mvar|a}}代表每一级递归的递归调用次数,{{mvar|b}}代表下一级递归的输入会小多少(即把问题分成多少块), {{math|''f''&thinsp;(''n'')}} 代表函数在每一级递归中独立于任何递归(如分割、重新组合)的工作。
    
==See also==
 
==See also==
370

个编辑