时间复杂度和运行时间有什么区别？它们是一样的吗？
时间复杂度和运行时间有什么区别？
14
- Harshay
1
11该术语的含义完全取决于其使用的背景。当你的老板问为什么“运行时间”是3小时时，他并不是在谈论算法复杂度。当你的教授询问一个算法的“运行时间”时，他可能并不要求你拿出秒表来计时。 - San Jacinto
7个回答
19
运行时间是指程序运行所需的时间。时间复杂度是当输入规模趋近于无穷时，运行时间的渐进行为的描述。
你可以说运行时间“是”O(n^2)或其他复杂度类别，因为这是描述复杂度类别和大O符号的惯用方式。实际上，运行时间不是一个复杂度类别，它要么是一个持续时间，要么是一个给出持续时间的函数。 “是O(n ^ 2)”是该函数的数学属性，而不是完整的表征。确切的运行时间可能是2036 * n ^ 2 + 17453 * n + 18464个CPU周期，或其他任何值。虽然你通常不需要知道这么详细的信息，而且它也可能取决于实际的输入以及输入的大小。
- Steve Jessop
3
随着输入规模趋近于无限大，是的。 - CodeYogi
可以说“算法的运行时间是O(n^2)”而不是说“算法的运行时间是O(n^2)”吗（即使用“运行时间”代替“运行时间”）？ - AlwaysLearning
@AlwaysLearning：没问题，我能理解。 - undefined
4
时间复杂度和运行时间是两个完全不同的概念。
时间复杂度是与算法相关的完全理论性概念，而运行时间是代码运行所需的时间，完全不涉及理论。
两个算法可能具有相同的时间复杂度，比如O(n^2)，但其中一个算法可能需要比另一个算法多两倍的运行时间。
- akaHuman
1
同意。但是当我们针对同一个问题有两种不同的方法时，比较不同方法的运行时间以确保我们正确计算时间复杂度是否明智？--从初学者的角度来看？ - learningIsFun
2
"运行时间"是指所考虑的算法：另一个算法可能能够在渐近意义下更快地解决相同问题，也就是说，运行时间更短。而"时间复杂度"则与所考虑的问题本身有关。它被定义为解决该问题的任何算法的最小运行时间。同样的区分也适用于算法成本的其他度量，例如内存、#处理器、通信量等。(Blum的加速定理证明了通常情况下"最小"时间可能无法达到...)
- Martin Ziegler
0
分析算法是确定执行它所需的资源（如时间和存储）量。大多数算法都设计为能够处理任意长度的输入。通常，算法的效率或运行时间被表述为将输入长度与步骤数（时间复杂度）或存储位置数（空间复杂度）相关联的函数。
- ayush
0
运行时间是衡量代码或程序完成所需操作次数的指标。这里的关键词是“操作”和“完成”，每个单独操作完成所需的时间可能会受到处理器、内存等因素的影响。
在运行时间方面，如果我们有两种不同的算法解决同一个问题，优化后的算法可能需要比未经优化的算法更长的时间才能完成，因为存在各种因素，如RAM、PC的当前状态（服务于其他程序）等，甚至是计算运行时间本身的函数。
因此，仅根据完成所需的操作次数来衡量算法的效率是不够的，而应该将时间与输入进行比较，这样可以消除所有外部因素，这正是时间复杂度所做的。
时间复杂度是衡量算法随着输入规模增加而变化的指标。
时间复杂度也可以从算法/代码背后的逻辑中计算出来。另一方面，当代码完成时，可以计算出运行时间。
- sule mohammed
0
时间复杂度是算法中操作次数的度量，因此对于特定算法而言是固定的。
运行时间是机器执行算法中这些操作所需的实际时钟时间，这取决于许多因素，如机器的配置、该机器的当前负载等等，因此它对于特定算法而言并不是固定的。
- Sohan Karfa
1
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接