时间戳

首页 > 解决方案 > 为什么下面代码片段的时间复杂度是 O(n) 而空间复杂度是 O(1)

time-complexity - 为什么下面代码片段的时间复杂度是 O(n) 而空间复杂度是 O(1)

问题描述

下面给出的代码的空间复杂度为 O(1)。我知道它与调用堆栈有关，但我无法正确地可视化它。如果有人能让我更清楚地理解这一点，那就太好了。

int pairSumSequence(int n) {
    int sum = 0;
    for (int i = 0;i < n; i++) {
        sum += pairSum(i, i + l);
    }
    return sum;
}

int pairSum(int a, int b) {

 return a + b;

}

标签： time-complexityspace-complexity

解决方案

相对于 的价值，它需要多少空间n？

唯一使用的变量是sum. sum关于 不会改变n，因此它是恒定的。

如果它是恒定的，那么它是 O(1)

相对于 的值，它将执行多少条指令n？

我们先简化代码，然后逐行分析。

int pairSumSequence(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += 2 * i + l;
    }
    return sum;
}

变量的声明和初始化需要恒定的时间，并且不随n. 因此这条线是O(1)。

int sum = 0;

同样返回一个值需要恒定的时间，所以它也是 O(1)

return sum;

最后我们来分析一下for的内部：

sum += 2 * i + l;

这也是常数时间，因为它基本上是一个乘法和两个和。再次O（1）。但是这个 O(1) 在 for 中被调用：

for (int i = 0; i < n; i++) {
   sum += 2 * i + l;
}

此 for 循环将准确执行n次数。因此，该函数的总复杂度为：

C = O(1) + n * O(1) + O(1) = O(n)

这意味着此函数将花费与的值成比例n的时间。

推荐阅读