如何可能O(1)的常数时间代码比O(n)的线性时间代码慢？

Question

如何可能O(1)的常数时间代码比O(n)的线性时间代码慢？

time-complexitybig-o

5

根据我的理解：

O(N) - 根据输入N的不同值运行算法所需的时间。
O(1) - 算法执行所需的恒定时间，无论输入的大小如 int val = arr[10000];

"...对于特定输入，O(N)代码非常可能比O(1)代码运行得更快。大O表示的只是增长速度。"

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

O(N)的代码比O(1)的代码运行更快吗？
作者指的是哪些具体的输入？
增长速度是指什么？

- Sri T

5

O(1) 表示无论输入的大小如何，该过程所需的时间大致相同。O(N) 表示时间与输入的大小成正比，因此如果将输入的大小加倍，则时间大致加倍。O 描述了处理过程所需时间随输入大小变化的方式。 - khelwood

O(1)的例子：while (true) { ; }。O(n)的例子：for (int i = 0; i < n; i++) { ; }。哪个需要更长时间？ - Erwin Bolwidt

O(1) 应该需要无限长的时间。 - Sri T

2个回答

2

考虑以下情况：

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

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

现在如果数组大小在10和20之间（不包括20），Op1将比Op2慢。但是假设我们取一个大小>20的数组（例如，size = 1000），Op1仍然需要20个步骤才能完成，但Op2需要1000个步骤才能完成。

这就是为什么大O符号表示算法复杂度的增长（增长率）。

- mettleap

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ggorlen · Accepted Answer

O(n)常数时间绝对可以比O(1)线性时间更快。原因是常数时间操作在大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});

很明显，常数级别的运行速度比线性级别要慢。

但是如果像这样调用：

int[] arr = new int[10000000];

constant(arr);
linear(arr);

哪个运行速度更慢？

在你思考过后，运行代码并比较各种输入下的结果。

仅为了展示这种情况不仅适用于常数时间函数，考虑以下内容：

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值？