463
个编辑
更改
跳到导航
跳到搜索
第488行：
第488行： − +
→运行时复杂性度量 Evaluating run-time complexity
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.
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)次(注意，终止 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 / 子时间。
步骤4、5和6中的循环更难计算。步骤4中的外部循环测试将执行(''n'' + 1)次（注意，终止 for 循环需要一个额外的步骤，因此循环次数是 n + 1 次而不是 n 次），这将消耗时间T4(n+1)。另一方面，内部循环由变量 j 的值控制，取值范围为 1 到 i。在第一次通过外循环时，j从1迭代到1：内循环进行一次传递，因此运行内循环（步骤6）消耗时间T6，内循环测试（步骤5）消耗时间为2T5。在下一次通过外部循环时，j 从1迭代到2: 内部循环进行两次后结束，因此运行内部循环体（步骤6）消耗时间为2T6，而内部循环测试（步骤5）消耗的时间为3T5。