时间复杂度究竟如何影响时间执行

Question

我写了一个简单的代码：

int temp = 10;

long startTime = System.currentTimeMillis();

for (int i = 0; i < temp; i++) {
    for (int j = 0; j < temp; j++) {
        for (int k = 0; k < temp; k++) {
            System.out.println(i + " " + j + " " + k);
        }
    }
}

long stopTime = System.currentTimeMillis();
System.out.println("Total Time: " + (stopTime - startTime));

此程序的总时间约为 50 毫秒。

但是，当我将温度更改为 100 时，我很难估计总时间大约为 500 毫秒（因为我们将温度提高了 10 倍 50*10=500），但另一方面我认为这是因为这是一个三次函数（时间复杂度为 O(n^3)）结果不应该正好是 500，它应该更多，因为随着温度的增加，总时间会根据其时间复杂度增加。实验后，我运行程序，结果是3234ms（一直在3000左右）。

那么，有人可以向我解释一下时间执行如何根据时间复杂度而变化吗？例如，如果我们有 10 个项目，执行时间为 50 毫秒，而对于 100 个项目，执行时间为 3000 毫秒，有人可以更精确地解释为什么会发生这种情况吗？

Answer 1

您必须意识到，永远不可能真正观察到渐近复杂性。

对于较小的 N（比如低于一千），低阶项不可忽略，测量没有意义，即使在理论上也是如此。

对于大 N（在 1000 到 10 亿之间），缓存和虚拟内存效应等因素起着重要作用并推翻了“恒定访问时间”假设。

对于非常大的N（十亿以上），机器容量耗尽。

Answer 2

一般而言，时间复杂度与特定输入的执行时间及其相关性无关。

对于您给出的例子，有如下评论：

转换为字符串和连接字符串，如在 i + " " + j + " " + k 中，将花费更长的时间，具体取决于生成的单个数字的数量。理论上，这样一种评估的时间复杂度为 O(log(ijk))
System.out.println 是一个复杂的野兽，取决于几个外部因素。您真的应该从要进行基准测试的代码中排除任何打印。
如果去掉打印、类型转换和字符串连接，那么时间复杂度确实是O(n³)，但是执行时间会包括低阶因子：比如声明j 发生 O(n) 次，而 k 的声明发生 O(n²) 次。鉴于不相关的整体时间复杂度，但在执行时间方面，它有所不同。

时间复杂度究竟如何影响时间执行

How exactly does time complexity affect time execution

java

algorithm

time

time-complexity