你问道：
如果时间复杂度为O(n^3)，那么如何证明实践中运行时间总是更接近于O(n^2)而不是O(n^3)？
答案是“更接近”并不重要，只有“大于”和“小于”才重要。
Big O给出了一个上限
如果一个过程的运行时复杂度最终超过c * n^2（其中c是任意常数或更大值，n足够大），那么它不可能是O(n^2)。
这是因为Big-O运算符不是给出估计，而是给出上限。即使一个在常数时间内运行的过程仍然是O(n^3)。 （它也是O(n^2)，O(log(n))，O(n!)等）。这是因为对于某些常数乘数c和大的n值，该过程比所有这些运行时间都小。
一个具体的例子
为了使这个问题具体化，请考虑以下内容：
>>> def fa(n):
... return n * n * n // 10
...
>>> def f2(n):
... return n * n
...
>>> def f3(n):
... return n * n * n
...
对于上述运行时和小的
n，
fa仍然小于或等于
f2：
>>> fa(10), f2(10), f3(10)
(100, 100, 1000)
但如果我们将n乘以10，fa就会超过f2。
>>> fa(100), f2(100), f3(100)
(100000, 10000, 1000000)
很容易看出，即使我们通过常数倍增加f2，仍然可以找到一个n值，使得fa(n)更大。
>>> def f2_boost(n, c):
... return f2(n) * c
...
>>> fa(1000), f2_boost(1000, 10), f3(1000)
(100000000, 10000000, 1000000000)
为什么使用常数乘法？
你可能仍然会感到困惑，一个运行时间为n^3 * 0.1的程序与一个运行时间为1000 * n^3的程序属于相同的大O类别。毕竟，这两个运行时间之间的绝对差异是巨大的!
这有点难以解释，但当你提醒自己，大O符号应该描述缩放行为时，它开始变得有意义。或者换句话说，大O符号应该描述运行时间如何随着我们更改用于测量的“单位”大小而变化。
让我们举个具体的例子：假设你想知道一幢建筑物的高度。并且假设有人说“哦，它大约300米。”你可能会对这个回答感到满意；你可能不在乎它实际上是315米；300是一个足够好的估计。但是如果他们说“哦，它大约300米......还是300英尺？”你可能会感到更不满意，因为300米是300英尺的三倍以上。
在计算机科学中，当测量时间时，我们恰好遇到了这个问题。事实上，情况甚至更糟。不同的计算机可能比其他计算机快得多或慢得多。如果我们以“计算机执行的计算次数”为单位来测量时间，那么对于一些计算机，我们将使用百分之几秒来测量时间，而对于其他计算机，我们将使用十亿分之一秒来测量时间。如果我们想用不会因这种巨大差异而偏斜的方式描述算法的行为，那么我们需要一个“规模不变”的测量——一个测量，无论我们使用百分之几秒还是十亿分之一秒作为单位，都会给出相同的答案。
大O符号提供了这样的测量。它给我们一种测量运行时间的方法，而不需要太担心我们用来测量时间的单位的大小。实际上，说一个算法是O(n^2)就是说，对于任何等于或大于某个值c的时间单位，存在相应的n值，使得我们的过程在所有更大的n值之前完成c * n^2。
估计运行时间
如果你想讨论估计运行时间，则需要一个称为“大theta”的测量。请查看此答案了解详情。简而言之，大O为任意大的乘数c提供了一个上限；大omega为任意大的乘数c提供了一个下限；大theta给出了一个函数，它根据乘数c的选择定义了上限和下限。
在您的情况下，大O值将为O(n^3)，因为您可以选择一个常数乘数c1，使得c1 * n^3始终大于n^3 / 10，并且您可以选择一个常数乘数c2，使得c2 * n^3始终小于n^3 / 10。
.1*O(N^3)仍然是O(N^3)，它并不更接近O(N^2)。 - mgilson