计算循环内循环的时间复杂度示例

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("*");
            }
        }
    }
}

这里是link上面的问题，https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/

请看第 7 题

上述函数的时间复杂度是多少？在这个问题上，他们说它是 O(n^5) 但我对此有一些疑问，有人能给我一些数学证明吗

Answer 1

我想可能是O(N^5)。第一个 for 循环的范围最大为 n，第二个 for 循环有 n^2（考虑最高系数项），最后一个与第二个相同。因此这些的乘法是 n^5.

Answer 2

首先，你的程序会崩溃，因为if(j % i == 0)，i和j都是0
稍微更改一下代码

void function(int n)
{
    int count = 0;
    for (int i=1; i<n; i++) // runs O(n) times
        for (int j=i; j< i*i; j++)  
            if (j%i == 0) // runs O(i) times
            {
                for (int k=0; k<j; k++) // runs j times, whenever j is factor of i
                    //that is when j = i, j = 2i ... j = i* i
                    printf("*");
            }
}

以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)

计算循环内循环的时间复杂度示例

Calulating time complexity of loops with in loops example

algorithm

asymptotic-complexity