463
个编辑
更改
跳到导航
跳到搜索
第585行：
第585行： − {{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 /> + + − − − − − − − + − − − − − − + − − − }}+ − − − 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> 第626行：
第609行： − Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]+ 第634行：
第617行： − −
→运行时复杂性度量 Evaluating run-time complexity
根据'''<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>)。证明如下：
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}
<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\\
&\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 )
\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>
\end{align}</math>
<br /><br />
<br /><br />
Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]
Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]
<br /><br />
<br /><br />
<math>\begin{align}
<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\\
&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
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
\end{align}</math>
\end{align}</math>
<br /><br />
<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>
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>
证明：<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 />
<br /><br />
<math>\begin{align}
<math>\begin{align}
\end{align}</math>
\end{align}</math>
<br /><br />
<br /><br />
设''k''为一个大于或等于[''T''<sub>1</sub>..''T''<sub>7</sub>]的常数：
<br /><br />
<br /><br />
<math>\begin{align}
<math>\begin{align}
<br /><br />
<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>
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>