时间复杂度和运行时间之间的差异 [英] Difference between Time Complexity and Running time

问题描述

只是想知道在一个问题中是否在谈论算法的运行时间，这是否意味着与时间复杂度相同，或者两者之间有什么区别？

Just wondering if in a question there is talk about the Running time of an algorithm, does it mean the same as Time Complexity or is there any difference between the two?

推荐答案

运行时间是程序运行所需的时间。时间复杂度是对运行时间随输入大小趋于无穷大的渐近行为的描述。

Running time is how long it takes a program to run. Time complexity is a description of the asymptotic behavior of running time as input size tends to infinity.

您可以说运行时间是 O（n ^ 2）之类的，因为这是描述复杂性类和big-O表示法的惯用方式。实际上，运行时间不是复杂度类，它是持续时间，或者是为您提供持续时间的函数。 成为O（n ^ 2）是该函数的数学特性，而不是其完整特征。确切的运行时间可能是2036 * n ^ 2 + 17453 * n + 18464个CPU周期，或其他任何时间。并不是您经常需要非常详细地了解它，无论如何，它很可能取决于实际输入以及输入的大小。

You can say that the running time "is" O(n^2) or whatever, because that's the idiomatic way to describe complexity classes and big-O notation. In fact the running time is not a complexity class, it's either a duration, or a function which gives you the duration. "Being O(n^2)" is a mathematical property of that function, not a full characterisation of it. The exact running time might be 2036*n^2 + 17453*n + 18464 CPU cycles, or whatever. Not that you very often need to know it in that much detail, and anyway it might well depend on the actual input as well as the size of the input.

这篇关于时间复杂度和运行时间之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！