java - 算法复杂度分析

Question

下面列出的两种方法的大 O 时间复杂度是多少？

方法 1 是 O(log n²) 还是 O(log n)？

方法 2 O(n²) 还是其他？

public static void method1(int n) {
    int k = 0;      
    for (int i = 1; i <= n; i = i*2)
       for (int j = n; j > 1; j = j/2)
           k++;     
}               

public static void method2(int n) {             
    for (int i = 1; i <= n; i = i + 1)
       for (int j = i; j <= n; j++)
          method1(n);
}

Answer 1

在第一种方法中你有 2 个嵌套循环，每个循环都是 log(n) 所以是的，这会将它们变成 O((logn)^2)

对于第二种方法，如果我们关注第二个循环，我们可以看到 for

• i = 1 => 运行 n 次
• i = 2 => 运行 n-1 次
• ...
• i = n => 运行 1 次

这是一个算术级数，它的总和等于 n * (n+1)/2 这将它变成了一个 O((nlogn)^2) 因为我们调用方法 1 大约 n^2 次。