时间复杂性和运行时间有什么不同？

问题描述

时间复杂性和运行时间的区别是什么？它们是相同的吗？

推荐答案

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

您可以说运行时间"是"O(n^2)或其他任何东西，因为这是描述复杂类和大O符号的惯用方式。事实上，运行时间不是一个复杂的类，它要么是一个持续时间，要么是一个给你持续时间的函数。"为O(n^2)"是该函数的一个数学性质，而不是它的完全刻画。确切的运行时间可能是2036*n^2+17453*n+18464个CPU周期，或者其他任何时间。这并不是说您经常需要非常详细地了解它，而且无论如何，它可能很好地取决于实际输入以及输入的大小。