算法复杂度分析

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

method1的复杂性是O((log )2)，因为我们有一个嵌套循环，每个循环运行O(log )次。

在Method2中，我们执行Method1的时间为三角图数，即执行O(n平方)次。由于我们执行O((log )2)函数O(N 2)次，因此Method2的复杂性为O(n平方⋅(log )2)。

Answer 2

在第一个示例中，外部循环执行logn次数，第二个循环也执行log n次。其复杂性为O(Log 2 n)。

在第二个示例中，第一循环执行n次，第二循环执行I次，其中i是第一循环的当前索引。因此，它执行1+ 2 +3+.+n次，之和为n⋅(n - 1) /2，计算复杂度为O( (n 2-n)n)=O(N 2 2)。在这里阅读更多1+2+3.系列

因此，为了结束它，method2执行method1 n 2次，给出了O(n平方⋅日志n)的总复杂性。

Answer 3

在第一个方法中，有两个嵌套循环，每个循环都是log(n)，所以是的，这会将它们转化为O((logn)^2)。

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

• I=1 =>运行n次
• I=2 =>运行n-1次
• ..。
• I=n =>运行1次

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