确定具有一个常数因子的嵌套循环的时间和 space 复杂度

Question

for 1 to n
 for j=1 to 3
    for i=j to n
       count++

我的答案：O(n^2)

如有错误请指正。谢谢

编辑：最内层循环的运行时间为 O(n) 以及最外层循环。但是 j=1 到 3 呢？

编辑 2：据我所知，如果存在 -

，则可以计算 Space 复杂度

• 变量声明
• 数据结构
• 分配
• 函数调用

但是上面的代码中有none个。那么 space 的复杂度是多少？

Answer 1

它是 O(n^2) 因为：

• 对于 1 是 O(n)
• 对于 2 是 O(1) - 最终操作数
• 对于 3 是 O(n) - i->n 仍然是 O(n) 因为顺序取决于 n

总结 - O(n^2).

Answer 2

解决这个问题的另一种方法是重写代码如下：

for x= 1 to n
    for i = 1 to n
        count++
    for i = 2 to n
        count++
    for i = 3 to n    // considering 1 to 3 => [1, 3]
        count++

那么，我们可以说所有内层循环的时间复杂度都是O(n)，即O(n) + O(n) + O(n) = O(n).

外循环的时间复杂度也是O(n)并且对于外循环的每次迭代我们在内循环中有O(n)次迭代使得它O(n^2).

此外，Space 复杂度为 O(1)，因为只有少数变量声明（声明的变量为：count、i、j ; 你也忘了在最外层循环中声明一个不依赖于任何外部参数的变量，即 Space 无论输入大小如何，复杂度都保持不变。