463
个编辑
更改
跳到导航
跳到搜索
第461行：
第461行： − 给定的计算机将采取一个离散的时间量来执行与执行这个算法有关的每一个指令。执行给定指令的具体时间量取决于正在执行的指令和正在执行的计算机，但在传统计算机上，这个时间量是确定的。假设步骤1中执行的动作被认为消耗时间 t 子1 / 子，步骤2使用时间 t 子2 / 子，等等。+ − − 第610行：
第608行： − {{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>}}+
→运行时复杂性度量 Evaluating run-time complexity
A given computer will take a discrete amount of time to execute each of the instructions involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be deterministic. Say that the actions carried out in step 1 are considered to consume time T<sub>1</sub>, step 2 uses time T<sub>2</sub>, and so forth.
A given computer will take a discrete amount of time to execute each of the instructions involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be deterministic. Say that the actions carried out in step 1 are considered to consume time T<sub>1</sub>, step 2 uses time T<sub>2</sub>, and so forth.
一台给定的计算机在执行算法有关的每一条指令时花费的时间是离散的。执行给定指令的具体时间量取决于正在执行的指令和正在执行的计算机，但在传统计算机上，这个时间量是确定的。假设在步骤1中执行的操作消耗时间为T1，步骤2的时间为T2，依此类推。
In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:
In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:
分析这个算法的一个更好的方法，是声明[''T''<sub>1</sub>..''T''<sub>7</sub>]都等于一个时间单位，在同一个单位制中，选择这样一个单位大于或等于这些步骤的实际时间。这意味着该算法的运行时间分解如下：
分析这个算法的一个更好的方法，是声明[''T''<sub>1</sub>..''T''<sub>7</sub>]都等于一个时间单位，在同一个单位制中，选择这样一个单位大于或等于这些步骤的实际时间。这意味着该算法的运行时间分解如下：
<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===