data-structures - 迭代程序的时间复杂度分析需要说明

Question

以下迭代程序的时间复杂度是多少？

void function(int n) {
    int count = 0; 
    for (int i=0; i<n; i++) 
        for (int j=i; j< i*i; j++) 
            if (j%i == 0) 
            { 
                for (int k=0; k<j; k++) 
                    printf("*"); 
            } 
}

标签： data-structures

Answer 1

 (n * n * n^2) 使三个循环的复杂度为 O(n^4)。

当 i = 5 时，

这意味着总体复杂性，

for (int j=5; j< 25; j++)  
     if (j%i == 0) // runs O(i) times
     {
      // runs j times when j = 5, 10, 15, 20
            for (int k=0; k<j; k++) {
                printf("*"); // runs j times when j =  5(1 + 2 + 3+ 4)
               // runs  j times which is i*i*(i*(i-1)/2) times
               // runs i^4 times
            }
     }

这意味着总复杂度为 O(n^4)。请记住，big-O 表示法用于给出一段代码的运行时间的上限，因此如果运行时间实际上是 O(n4)，则说运行时间是 O(n5) 不是错误的; 它只是不紧。