463
个编辑
更改
→运行时复杂性度量 Evaluating run-time complexity
作为一个经验法则，我们可以假设任何给定函数中的最高阶项主导了它的增长率，从而定义了它的运行时序。在这个例子中，n sup 2 / sup 是最高阶项，因此可以得出 f (n) o (n sup 2 / sup)。在形式上，这可以证明如下:
作为一个经验法则，我们可以假设任何给定函数中的最高阶项主导了它的增长率，从而定义了它的运行时序。在这个例子中，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>
{{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>
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 />