简单循环的大 O 表示法

Question

我刚开始学习数据结构class，老师们发了10个问题，问了其中一个的大O。根据我读过的帖子，我假设这段代码的大 O 是 O(1)，因为数据参数是单个数据元素。但是，它确实会根据数字的大小执行多次，所以这会使它成为 O(N)?

public class Main {

    public static void main(String[] args) {
        f(100000);
    }

    public static long f (int n) {
        long sum = 0;
        for (long i = 2; i < n; i = i * i) {
            sum += i;
            System.out.println(sum);
        }
        return sum;
    } // end f
}

Answer 1

这个函数的时间复杂度为O(log(log(n))。

i 通过乘以一个指数增长的因子来增长，所以这就是 "double exponential growth"（不确定这是否是一个有效的定义），复杂度是相反的。您可以阅读有关此 class 复杂性 here.

的更多信息

Answer 2

使用 Sigma 符号分析您的算法

要严格分析算法的增长，可以使用如下 Sigma 表示法：

与：

我们还假设，在使用 (*) 结果的等式中，对于某个正整数 j。对于此假设不成立的 n 的值，只需删除上面 k 的总和中的 floor function。

结果：对数-对数时间复杂度

从上面可以看出，您的算法显然具有 log-logarithmic 时间复杂度，即（渐近上限）O(log(log n)).

简单循环的大 O 表示法

Big O Notation for simple loop

big-o

使用 Sigma 符号分析您的算法

结果：对数-对数时间复杂度