运行 时间、复杂性、编译时间和执行时间有什么区别？
what is the difference between running time ,complexity,compile time and execution time?
运行时间、复杂度、编译时间和执行时间有什么区别？
我在运行时间和时间复杂度之间有冲突，它们和执行时间有什么区别？
Execution Time 是您的程序执行所需的时间。例如，10 秒或 10 毫秒。
复杂性 通常是指算法的渐近行为。简而言之，它表明 你的算法 是高效的。在这方面我们通常使用时间复杂度和Space复杂度。时间复杂度渐进地显示你的算法有多快 运行 和 Space 复杂度显示你的算法将使用多少内存位。这是使用大 O、小 o、Theta 等符号的地方。 （看
TimeComplexity)
运行 time 可以与执行时间（程序终止所需的时间）互换使用。但是，通常当程序在 运行ning 时发生某些错误时，他们通常也会通过 a 运行time error 来引用它。
另外编译时间是程序编译并转换为可执行文件所花费的时间。
另见 RunTime, ExecutionTime and CompileTime。
你真正想问的是如何将Big O时间复杂度转化为运行时。这并不像一开始看起来那么容易。
所以先仔细看看复杂性，为了让它更简单，让我们使用这个简单的 C++ 示例：
int fact(int n)
{
if (n<=1) return 1;
return n*fact(n-1);
}
时间与 Space 复杂度
（对于初学者，我假设基本变量因此所有复杂性都与基础相同，更多信息请参见下一个项目符号）因此整个事情将进行 n 次迭代，这意味着 O(n) 时间复杂度。由于这对单个辅助结果使用堆栈递归和堆，因此 space 复杂度也是 O(n).
基本复杂度与真实复杂度
Base complexity 是所用算法的复杂度。但是当实现到程序中时，由于变量实现、IO 协议等因素，复杂性可能会发生变化（变得更糟）
例如，如果我们使用 bigint 而不是 int 会怎样？该程序是相同的，因此基本复杂性保持不变 O(n)。 bigints 的问题在于它们不是 O(1) space 复杂性（更像是 O(log(n))）并且对它们的操作也不是 O(1)了。例如，如果 (m=log(n)) 则 (+,-,&,|,^) 操作是 O(m)，mutliply 最多可以变化 O(m^2)。因此，当使用 O(m^2) 乘法时，时间复杂度将为 O(n.log(n).log(n))。 Space 复杂度也更差 O(n.log(n)).
问题是大多数菜鸟只使用算法的基本复杂度，而不是整个实现的复杂度，导致结果模糊不清。现在的另一个问题是在没有任何背景知识的情况下滥用库和框架。
计算运行时间
编程中的这种热有时被认为是矛盾的。没有可靠的方法可以将复杂性转换为任意实现的运行时。为什么？因为运行时依赖太多东西，比如：
展位Space & 时间复杂度
现代架构使用流水线、超级缩放、缓存等。因此，当您遇到 space 障碍时，性能可能会改变 多次 通常变得更糟。
硬件平台
每个平台都不一样。 pipelines/cache 大小的配置、其管理策略、延迟等即使在类似功率 CPU 之间的比较也会产生巨大差异。 HW 平台上的功能远不止 CPU。每个模块使用计数（内存，HDD，DMA，gfx...）
编译器
每个编译器都有自己的怪癖、优化等导致不同的程序集输出。这可能导致在不同编译器上编译的相同源代码的可执行文件之间存在巨大差异。
OS
OS 比您的应用程序运行得更多。有服务，中断，维护任务，其他进程都会影响运行时。
编程风格
这也能行。大多数编程风格差异通常会被编译器优化所抵消，但不是全部。例如迭代首选项之前的递归会对运行时产生巨大的（通常是负面的）影响。
优化
如果您在汇编中查看未优化的代码和优化的代码，您通常会不再识别这些代码。这不应该影响程序的基本复杂性，但如果可以的话，通常会改变真正的复杂性。
我也写了几十年代码，所以我习惯自己优化我的代码。这种偏好有时会误导现代编译器，并在极少数情况下导致生成的代码变慢。
那么Runtime如何计算呢？
你根本做不到，你能做的最好的就是测量 + 估计。
- 测量任务开始时的时间
t0
测量任务期间的时间（不时）
例如每秒，或每 1000th 次迭代……记住时间 t 和迭代 i。这有时称为运行时间。
预测剩余时间。
所以如果我们有时间复杂度O(n)那么（如果我没记错的话）：
t(0) = t0
t(i) = ti ~= t0 + T*i -> T ~= (ti-t0)/i
t(n) = t0+T*n ~= t0 + (ti-t0)*n/i
您可以在计算过程中平均或更新此时间，因此每次新测量都会越来越准确。此外，有时最好根据最近几次测量 t(i) 和 t(j) 来评估运行时间，因为处理能力会随时间发生变化。
在高精度测量时间时注意 OS 粒度参见
- wrong clock cycle measurements with rdtsc
如果不考虑，它可能会误导您的计算。但这仅在您想要测量非常快的过程时才重要，我认为情况并非如此。
PS.
这一切只适用于足够大的情况 n 否则从复杂性中丢弃的热量仍然很重要并对结果的准确性产生负面影响。
编译时间
如其他答案中所述，这是编译器需要处理您的源代码的时间。这与程序复杂度无关。这主要受包括递归级别、源代码长度、宏使用和递归、模板使用等的影响。
通常，通过简单地重新排序 #include 顺序并避免多次包含，您可以显着缩短编译时间。很好的例子是来自 Atmel 的 AVR32 框架……调整后编译时间可以缩短 100 倍甚至更多。有一次我看到（10 多年前）一个有 300MB 源代码的打印机固件（当时），由于包含滥用，编译时间略少于一小时……考虑到它是单个代码，这太疯狂了单片机 ...
希望对您有所帮助
运行时间、复杂度、编译时间和执行时间有什么区别？ 我在运行时间和时间复杂度之间有冲突，它们和执行时间有什么区别？
Execution Time 是您的程序执行所需的时间。例如，10 秒或 10 毫秒。
复杂性 通常是指算法的渐近行为。简而言之，它表明 你的算法 是高效的。在这方面我们通常使用时间复杂度和Space复杂度。时间复杂度渐进地显示你的算法有多快 运行 和 Space 复杂度显示你的算法将使用多少内存位。这是使用大 O、小 o、Theta 等符号的地方。 （看 TimeComplexity)
运行 time 可以与执行时间（程序终止所需的时间）互换使用。但是，通常当程序在 运行ning 时发生某些错误时，他们通常也会通过 a 运行time error 来引用它。
另外编译时间是程序编译并转换为可执行文件所花费的时间。
另见 RunTime, ExecutionTime and CompileTime。
你真正想问的是如何将Big O时间复杂度转化为运行时。这并不像一开始看起来那么容易。
所以先仔细看看复杂性，为了让它更简单，让我们使用这个简单的 C++ 示例：
int fact(int n)
{
if (n<=1) return 1;
return n*fact(n-1);
}
时间与 Space 复杂度
（对于初学者，我假设基本变量因此所有复杂性都与基础相同，更多信息请参见下一个项目符号）因此整个事情将进行
n次迭代，这意味着O(n)时间复杂度。由于这对单个辅助结果使用堆栈递归和堆，因此 space 复杂度也是O(n).基本复杂度与真实复杂度
Base complexity 是所用算法的复杂度。但是当实现到程序中时，由于变量实现、IO 协议等因素，复杂性可能会发生变化（变得更糟）
例如，如果我们使用 bigint 而不是
int会怎样？该程序是相同的，因此基本复杂性保持不变O(n)。 bigints 的问题在于它们不是O(1)space 复杂性（更像是O(log(n))）并且对它们的操作也不是O(1)了。例如，如果 (m=log(n)) 则(+,-,&,|,^)操作是O(m)，mutliply 最多可以变化O(m^2)。因此，当使用O(m^2)乘法时，时间复杂度将为O(n.log(n).log(n))。 Space 复杂度也更差O(n.log(n)).问题是大多数菜鸟只使用算法的基本复杂度，而不是整个实现的复杂度，导致结果模糊不清。现在的另一个问题是在没有任何背景知识的情况下滥用库和框架。
计算运行时间
编程中的这种热有时被认为是矛盾的。没有可靠的方法可以将复杂性转换为任意实现的运行时。为什么？因为运行时依赖太多东西，比如：
展位Space & 时间复杂度
现代架构使用流水线、超级缩放、缓存等。因此，当您遇到 space 障碍时，性能可能会改变 多次 通常变得更糟。
硬件平台
每个平台都不一样。 pipelines/cache 大小的配置、其管理策略、延迟等即使在类似功率 CPU 之间的比较也会产生巨大差异。 HW 平台上的功能远不止 CPU。每个模块使用计数（内存，HDD，DMA，gfx...）
编译器
每个编译器都有自己的怪癖、优化等导致不同的程序集输出。这可能导致在不同编译器上编译的相同源代码的可执行文件之间存在巨大差异。
OS
OS 比您的应用程序运行得更多。有服务，中断，维护任务，其他进程都会影响运行时。
编程风格
这也能行。大多数编程风格差异通常会被编译器优化所抵消，但不是全部。例如迭代首选项之前的递归会对运行时产生巨大的（通常是负面的）影响。
优化
如果您在汇编中查看未优化的代码和优化的代码，您通常会不再识别这些代码。这不应该影响程序的基本复杂性，但如果可以的话，通常会改变真正的复杂性。
我也写了几十年代码，所以我习惯自己优化我的代码。这种偏好有时会误导现代编译器，并在极少数情况下导致生成的代码变慢。
那么Runtime如何计算呢？
你根本做不到，你能做的最好的就是测量 + 估计。
- 测量任务开始时的时间
t0 测量任务期间的时间（不时）
例如每秒，或每
1000th次迭代……记住时间t和迭代i。这有时称为运行时间。预测剩余时间。
所以如果我们有时间复杂度
O(n)那么（如果我没记错的话）：t(0) = t0 t(i) = ti ~= t0 + T*i -> T ~= (ti-t0)/i t(n) = t0+T*n ~= t0 + (ti-t0)*n/i您可以在计算过程中平均或更新此时间，因此每次新测量都会越来越准确。此外，有时最好根据最近几次测量
t(i)和t(j)来评估运行时间，因为处理能力会随时间发生变化。在高精度测量时间时注意 OS 粒度参见
- wrong clock cycle measurements with rdtsc
如果不考虑，它可能会误导您的计算。但这仅在您想要测量非常快的过程时才重要，我认为情况并非如此。
PS.
这一切只适用于足够大的情况 n 否则从复杂性中丢弃的热量仍然很重要并对结果的准确性产生负面影响。
编译时间
如其他答案中所述，这是编译器需要处理您的源代码的时间。这与程序复杂度无关。这主要受包括递归级别、源代码长度、宏使用和递归、模板使用等的影响。
通常，通过简单地重新排序 #include 顺序并避免多次包含，您可以显着缩短编译时间。很好的例子是来自 Atmel 的 AVR32 框架……调整后编译时间可以缩短 100 倍甚至更多。有一次我看到（10 多年前）一个有 300MB 源代码的打印机固件（当时），由于包含滥用，编译时间略少于一小时……考虑到它是单个代码，这太疯狂了单片机 ...
希望对您有所帮助