463
个编辑
更改
→运行时复杂性度量 Evaluating run-time complexity
1 ''get a positive integer n from input''
1 ''get a positive integer n from input''
2 '''if''' n > 10
2 '''if''' n > 10
3 '''print''' "This might take a while..."
3 '''print''' "This might take a while..."
4 '''for''' i = 1 '''to''' n
4 '''for''' i = 1 '''to''' n
5 '''for''' j = 1 '''to''' i
5 '''for''' j = 1 '''to''' i
6 '''print''' i * j
6 '''print''' i * j
7 '''print''' "Done!"
7 '''print''' "Done!"
As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n<sup>2</sup> is the highest-order term, so one can conclude that f(n) = O(n<sup>2</sup>). Formally this can be proven as follows:
As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n<sup>2</sup> is the highest-order term, so one can conclude that f(n) = O(n<sup>2</sup>). Formally this can be proven as follows:
根据'''<font color="#ff8000">经验法则 Rule-of-thumb</font>'''，我们可以假设任意给定函数中的最高阶项主导其增长率，从而定义其运行时顺序。在这个例子中，最高阶项为n<sup>2</sup>，因此可以得出f(n) = O(n<sup>2</sup>)。证明如下：
根据'''<font color="#ff8000">经验法则 Rule-of-thumb</font>'''，我们可以假设任意给定函数中的最高阶项主导其增长率，从而定义其运行时顺序。在这个例子中，最高阶项为n<sup>2</sup>，因此可以得出f(n) = O(n<sup>2</sup>)。证明如下：
}}
}}
{{quote|Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>
<br /><br />
<math>\begin{align}
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
\le &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
\end{align}</math>
<br /><br />
Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]
<br /><br />
<math>\begin{align}
&T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
\end{align}</math>
<br /><br />
Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
}}