O(1) 常数时间码怎么可能比 O(n) 线性时间码慢？

Question

“...对于特定输入，O(N) 代码很可能比 O(1) 代码运行得更快。大 O 只是描述了增长率。”

根据我的理解：

• O(N) - 基于输入 N 的变化值运行算法所需的时间。
• O(1) - 无论输入大小如何，算法执行所需的时间都是恒定的，例如 int val = arr[10000];

有人可以根据作者的陈述帮助我理解吗？

1. O(N) 代码比 O(1) 运行得更快？
2. 作者暗指的具体输入是什么？
3. 增长率是多少？

Answer 1

O(n) 恒定时间绝对可以比 O(1) 线性时间快。原因是在 Big O 中完全忽略了恒定时间操作，这是衡量算法复杂性随着输入大小n增加而增加的速度的度量，仅此而已。它衡量的是增长率，而不是运行时间。

下面是一个例子：

int constant(int[] arr) {
    int total = 0;

    for (int i = 0; i < 10000; i++) {
         total += arr[0];
    }

    return total;
}
   
int linear(int[] arr) {
    int total = 0;        

    for (int i = 0; i < arr.length; i++) {
        total += arr[i];
    }

    return total;
}

在这种情况下，constant做了很多工作，但无论有多大，它都是固定的工作，它总是相同的arr。linear另一方面，似乎有很少的操作，但这些操作取决于 的大小arr。

换句话说，随着arr长度的增加，constant的性能保持不变，但linear的运行时间与其参数数组的大小成比例地线性增加。

使用单项数组调用这两个函数，例如

constant(new int[] {1}); 
linear(new int[] {1});

很明显，constant运行速度比linear.

但是这样称呼它们：

int[] arr = new int[10000000];

constant(arr);
linear(arr);

哪个跑得慢？

考虑好之后，在给定n 的各种输入的情况下运行代码并比较结果。

只是为了表明这种现象run time != Big O不仅适用于恒定时间函数，请考虑：

void exponential(int n) throws InterruptedException {
    for (int i = 0; i < Math.pow(2, n); i++) {
        Thread.sleep(1);
    }
}

void linear(int n) throws InterruptedException {
    for (int i = 0; i < n; i++) {
        Thread.sleep(10);
    }
}

练习（使用笔和纸）：高达哪些n不exponential运行的速度比linear？