463
个编辑
更改
→运行时复杂性度量 Evaluating run-time complexity
The [[program loop|loops]] in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( ''n'' + 1 )
The [[program loop|loops]] in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( ''n'' + 1 )times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume ''T''<sub>4</sub>( ''n'' + 1 ) time. The inner loop, on the other hand, is governed by the value of j, which [[iteration|iterates]] from 1 to ''i''. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes ''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 2''T''<sub>5</sub> time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 3''T''<sub>5</sub> time.
The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 )
The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 )times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume T<sub>4</sub>( n + 1 ) time. The inner loop, on the other hand, is governed by the value of j, which iterates from 1 to i. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes T<sub>6</sub> time, and the inner loop test (step 5) consumes 2T<sub>5</sub> time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2T<sub>6</sub> time, and the inner loop test (step 5) consumes 3T<sub>5</sub> time.
步骤4、5和6中的循环更难计算。步骤4中的外部循环测试将执行(n + 1)
步骤4、5和6中的循环更难计算。步骤4中的外部循环测试将执行(n + 1)次(注意，终止 for 循环需要一个额外的步骤，因此 n + 1而不是 n 次执行) ，这将消耗 t 小于4 / sub (n + 1)的时间。另一方面，内部循环由 j 的值控制，该值从1迭代到 i。在第一次通过外部循环时，j 迭代1到1: 内部循环通过一次，因此运行内部循环体(第6步)消耗 t 小于6 / 子时间，而内部循环测试(第5步)消耗2T 小于5 / 子时间。在下一次通过外部循环时，j 从1到2迭代: 内部循环进行两次通过，因此运行内部循环体(步骤6)消耗2T 子6 / 子时间，而内部循环测试(步骤5)消耗3T 子5 / 子时间。
{{quote|<math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \ (\text{for } n \ge 1) =O(n^2).</math>}}
{{quote|<math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \ (\text{for } n \ge 1) =O(n^2).</math>}}
===其他资源增长率分析 Growth rate analysis of other resources===
===其他资源增长率分析 Growth rate analysis of other resources===