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);

哪个运行速度较慢？

考虑了之后，run the code here给出了[[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运行到哪个速度快？    

Answer 2

请考虑以下情形：

Op1）给定长度为n的数组，其中n> = 10，请在控制台上两次打印前十个元素。 ->这是一个恒定时间（O（1））操作，因为对于任何大小> = 10的数组，它将执行20个步骤。

Op2）给定长度为n的数组，其中n> = 10，找到数组中最大的元素。这是一个恒定时间（O（N））操作，因为对于任何数组，它将执行N个步骤。

现在，如果数组大小在10到20（不包括）之间，则Op1将比Op2慢。但是，假设我们采用一个尺寸大于20（例如，尺寸= 1000）的数组，Op1仍然需要20步才能完成，而Op2则需要1000步才能完成。

这就是为什么big-o表示关于算法复杂度的增长（增长率）的原因>>