这些嵌套循环的大O

Question

我对“大O”领域很陌生，所以请容忍我在这里。我一直在尽我所能地寻找它，但我仍然需要大量的工作才能完全理解它。

我在练习中遇到了这些嵌套的for循环，没有任何解决方案，它们看起来很复杂。因此，任何帮助都将不胜感激。

1)

int sum=0;
for(int i=0; i < n^2; i++) { // n+1
    for(int j = n-1; j >= n-1-i; j–-) { // n(n+1)/2 ?
        sum = i+j; // n(n+1)/2 ?
        System.out.println(sum); // n(n+1)/2 ?
    }
}

大O=？

2)

int sum=0;
for(int i=1; i <= 2^n; i=i*2) { // log(n)
    for(int j=0; j <= log(i); j++) { // log(n(n+1)/2) ?
        sum = i+j; // log(n(n+1)/2) ?
        System.out.println(sum); // log(n(n+1)/2) ?
    }
}

大O=？

3)

int sum = 0; int k = 23;
for(int i=k; i <= 2^(n−k); i=i*2) { // log(n)
    for(int j=2^(i−k); j < 2^(i+k); j=j*2) { // log(log(n)) ?
        sum = i+j; // log(log(n)) ?
        System.out.println(sum); // log(log(n)) ?
    }
}

大O=？

4)

int sum=0;
for(int i=2n; i>=1; i=i/2) {
    for(int j=i; j>=1; j=j/2) {
        sum = i+j;
        System.out.println(sum);
    }
}

大O=？

编辑：

• 更正#4。抱歉搞砸了。
• 原木的底座是2。
• ^在这里的意思是“到电源”，而不是xor。

Answer 1

使用Sigma符号系统地为您的迭代算法找到解决方案：

​

​

在下面的日志中使用基2：

​

​

​

​

​

​