运行 时间和算法中的执行时间之间的差异？
Difference between Running time and Execution time in algorithm?
我目前正在阅读名为 CLRS 2.2 第 25 页的这本书。其中作者将算法的 运行 时间描述为
The running time of an algorithm on a particular input is the number of primitive
operations or “steps” executed.
另外作者利用运行的时间来分析算法。然后我参考了 Narasimha Karumanchi 写的一本名为《数据结构和算法》的书。
他在其中描述了以下内容。
1.7 Goal of the Analysis of Algorithms
The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of
running time but also in terms of other factors (e.g., memory, developer effort, etc.)
1.9 How to Compare Algorithms:
To compare algorithms, let us define a few objective measures:
Execution times? Not a good measure as execution times are specific to a particular computer.
Number of statements executed? Not a good measure, since the number of statements varies
with the programming language as well as the style of the individual programmer.
Ideal solution? Let us assume that we express the running time of a given algorithm as a function
of the input size n (i.e., f(n)) and compare these different functions corresponding to running
times. This kind of comparison is independent of machine time, programming style, etc.
正如您从 CLRS 中看到的那样，作者将 运行 时间描述为执行的 步数 而在第二本书中，作者说其 不是一个很好的衡量标准 使用执行的步数来分析算法。 运行 时间也取决于计算机（我的假设），但第二本书的作者说我们不能考虑执行时间来分析算法，因为它完全取决于计算机。
我以为执行时间和运行时间一样！
所以，
- 运行时间和执行时间的真正含义或定义是什么？它们是相同的还是不同的？
- 运行时间是否描述了步数是否执行？
- 运行时间是否取决于电脑？
提前致谢。
What is the real meaning or definition of running time and execution time? Are they the same of different?
'Introduction to Algorithms' by C,L,R,S [CLRS]中定义的“运行时间”其实不是一个时间，而是一些步骤。这不是您直观地用作定义的内容。大多数人会同意“运行”和“执行”是同一个概念，而“时间”的单位是time（如毫秒）。因此，虽然我们通常认为这两个术语具有相同的含义，但在 CLRS 中它们已经偏离了这一点，并赋予“运行 时间”不同的含义。
Does running time describe the number of steps executed or not?
在 CLRS 中确实是这样。但是 CLRS 对“运行 时间”使用的定义是特殊的，与您在其他资源中可能遇到的定义不同。
CLRS 假设 原始操作（即一个步骤）需要 O(1) 时间。
这通常适用于 CPU 指令，它最多占用固定的最大周期数（其中每个周期代表一个时间单位），但在高级语言中可能并非如此。例如，某些语言有 sort 指令。将其计为一个“步骤”将在分析中给出无用的结果。
将算法分解为 O(1) 个步骤确实有助于分析算法的复杂性。 计算 不同输入的步骤可能只会给出有关复杂性的提示。最终，算法的复杂性需要基于循环和算法中使用的步骤的已知复杂性的（数学）证明。
Does running time depend on the computer or not?
当然，执行时间可能不同。这是我们偶尔想使用新计算机的原因之一。
步数可能取决于计算机。如果两者都支持相同的编程语言，并且您使用 那种 语言计算步骤，那么：是的。但是，如果您更彻底地进行计数，并计算编译程序实际上 运行 的 CPU 条指令，那么它可能会有所不同。例如，一台计算机上的 C 编译器生成的机器代码可能与另一台计算机上的不同 C 编译器生成的机器代码不同，因此 CPU 指令的数量可能比另一台少，即使它们是由相同的 C 程序代码。
然而实际上，CPU 指令级别的这种计数与确定算法的复杂性无关。我们通常知道高级语言中每条指令的时间复杂度，这就是决定算法整体复杂度的重要因素。
我目前正在阅读名为 CLRS 2.2 第 25 页的这本书。其中作者将算法的 运行 时间描述为
The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed.
另外作者利用运行的时间来分析算法。然后我参考了 Narasimha Karumanchi 写的一本名为《数据结构和算法》的书。 他在其中描述了以下内容。
1.7 Goal of the Analysis of Algorithms The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g., memory, developer effort, etc.)
1.9 How to Compare Algorithms: To compare algorithms, let us define a few objective measures:
Execution times? Not a good measure as execution times are specific to a particular computer.
Number of statements executed? Not a good measure, since the number of statements varies with the programming language as well as the style of the individual programmer.
Ideal solution? Let us assume that we express the running time of a given algorithm as a function of the input size n (i.e., f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style, etc.
正如您从 CLRS 中看到的那样，作者将 运行 时间描述为执行的 步数 而在第二本书中，作者说其 不是一个很好的衡量标准 使用执行的步数来分析算法。 运行 时间也取决于计算机（我的假设），但第二本书的作者说我们不能考虑执行时间来分析算法，因为它完全取决于计算机。
我以为执行时间和运行时间一样！
所以，
- 运行时间和执行时间的真正含义或定义是什么？它们是相同的还是不同的？
- 运行时间是否描述了步数是否执行？
- 运行时间是否取决于电脑？
提前致谢。
What is the real meaning or definition of running time and execution time? Are they the same of different?
'Introduction to Algorithms' by C,L,R,S [CLRS]中定义的“运行时间”其实不是一个时间，而是一些步骤。这不是您直观地用作定义的内容。大多数人会同意“运行”和“执行”是同一个概念，而“时间”的单位是time（如毫秒）。因此，虽然我们通常认为这两个术语具有相同的含义，但在 CLRS 中它们已经偏离了这一点，并赋予“运行 时间”不同的含义。
Does running time describe the number of steps executed or not?
在 CLRS 中确实是这样。但是 CLRS 对“运行 时间”使用的定义是特殊的，与您在其他资源中可能遇到的定义不同。
CLRS 假设 原始操作（即一个步骤）需要 O(1) 时间。
这通常适用于 CPU 指令，它最多占用固定的最大周期数（其中每个周期代表一个时间单位），但在高级语言中可能并非如此。例如，某些语言有 sort 指令。将其计为一个“步骤”将在分析中给出无用的结果。
将算法分解为 O(1) 个步骤确实有助于分析算法的复杂性。 计算 不同输入的步骤可能只会给出有关复杂性的提示。最终，算法的复杂性需要基于循环和算法中使用的步骤的已知复杂性的（数学）证明。
Does running time depend on the computer or not?
当然，执行时间可能不同。这是我们偶尔想使用新计算机的原因之一。
步数可能取决于计算机。如果两者都支持相同的编程语言，并且您使用 那种 语言计算步骤，那么：是的。但是，如果您更彻底地进行计数，并计算编译程序实际上 运行 的 CPU 条指令，那么它可能会有所不同。例如，一台计算机上的 C 编译器生成的机器代码可能与另一台计算机上的不同 C 编译器生成的机器代码不同，因此 CPU 指令的数量可能比另一台少，即使它们是由相同的 C 程序代码。
然而实际上，CPU 指令级别的这种计数与确定算法的复杂性无关。我们通常知道高级语言中每条指令的时间复杂度，这就是决定算法整体复杂度的重要因素。