时间复杂度

Question

我正在尝试找出这些过程的时间复杂度，但我不确定它们是否好。

我认为这是 O(n)

static void P1(int n ){
   for (int i=1; i<=n; i++) {
      Procedure();
}

我认为这是 O(n^2)

static void P2(int n) {
   for(int i=1; i<=n; i++) 
    for(int j=1; j<=n; j++)
      Procedure();
}

O(n)+O(n)

static void P3(int n) {
   for (int i = 1; i <= n; i++)
     Procedure();
   for (int i = 1; i <= n; i++)
     Procedure();
}

100+n+100?

static void P4(int n) {
   for ( int i = 1; i <= 100; i++)
     for (int j = 1; j <= n; j++)
       for (int k = 1; k <= 100; k++)
         Procedure();
}

O(n*i)?

static void P5(int n) {
   for ( int i = 1; i <= n; i++)
     for (int j = 1; j <= i; j++)
       Procedure();
}

?

static void P6(int n) {
   for (int i = 1; i <= n/2; i++)
     for ( int j = 1; j <= n/4; j++)
       for (int k = 1; k <= n/8; k++)
         Procedure();
}

Answer 1

如果 Procedure() 是 O(1)，则：

我认为这是 O(n) 正确

static void P1(int n ){
   for (int i=1; i<=n; i++) {
      Procedure();
}

我认为这是 O(n^2) 正确

static void P2(int n) {
   for(int i=1; i<=n; i++) 
    for(int j=1; j<=n; j++)
      Procedure();
}

O(n)+O(n) 正确，但是 O(n+n)=O(2n)=O(n)

static void P3(int n) {
   for (int i = 1; i <= n; i++)
     Procedure();
   for (int i = 1; i <= n; i++)
     Procedure();
}

100+n+100？ false，它是相乘的：O(100*n*100)=O(n)

static void P4(int n) {
   for ( int i = 1; i <= 100; i++)
     for (int j = 1; j <= n; j++)
       for (int k = 1; k <= 100; k++)
         Procedure();
}

O(n*i)? 你不能使用 i 它没有确切的值。如果你看内循环执行了多少次，是1+2+3+4+...+n-3+n-2+n-1，也就是n*(n-1)/2，你可以把它相乘：n*(n-1)/2=n^2/2-n/2渐近n^2/2-n/2=Theta(n^2)

结果为O(n^2)

static void P5(int n) {
   for ( int i = 1; i <= n; i++)
     for (int j = 1; j <= i; j++)
       Procedure();
}

n/2 * n/4 * n/8 = n^3/64 = O(n^3)

static void P6(int n) {
   for (int i = 1; i <= n/2; i++)
     for ( int j = 1; j <= n/4; j++)
       for (int k = 1; k <= n/8; k++)
         Procedure();
}

Answer 2

的时间复杂度

static void P3(int n){
   for (int i = 1; i <= n; i++)
     Procedure();
   for (int i = 1; i <= n; i++)
     Procedure();
}

可以写成 O(2n) 的函数，因为我们需要消除常数，它变成 O(n)

的时间复杂度

static void P4(int n) {
   for ( int i = 1; i <= 100; i++)
     for (int j = 1; j <= n; j++)
       for (int k = 1; k <= 100; k++)
         Procedure();
}

100+n+100 => O(n*100*100) => O(n)

的时间复杂度

static void P6(int n) {
   for (int i = 1; i <= n/2; i++)
     for ( int j = 1; j <= n/4; j++)
       for (int k = 1; k <= n/8; k++)
         Procedure();
}

是 O(n^3)

请记住，我们不是在使用时间复杂度计算计算机执行的 no.of 条指令。 Big-O 只是告诉我们的执行时间如何随着输入的增加或减少而变化。

考虑阅读 Time Complexity

时间复杂度

Time complexity

java

time

complexity-theory