时间戳

首页 > 解决方案 > 多个嵌套 for 循环的时间复杂度是多少？

algorithm - 多个嵌套 for 循环的时间复杂度是多少？

问题描述

如何计算多个嵌套循环的时间复杂度？我已经完成了这段代码，但对它的时间复杂度感到困惑！

for(i=0; i<max; i++)
{
    for(j=0; j<max; j++)
    {
        a[i][j]= rand()%2;
    }
}

for(i=0; i<max; i++)
{
    for(j=0; j<max; j++)
    {

        if(a[j][i]==1)
        {
            inD++;
        }
    }
}
for(i=0; i<max; i++)
{
    for(j=0; j<max; j++)
    {
         if(a[i][j]==1)
         {
             outD++;
         }
    }
}

标签： algorithmtime-complexitybig-o

解决方案

你有三个循环。让我们拿第一个。

外部循环运行max时间，每次通过该循环都运行内部循环max时间，总共max * max调用a[i][j]= rand()%2;。每次调用都会生成一个随机数：我不知道这样做的成本是多少，但它独立于max. 这个循环的成本是O(max^2)。

其他两个循环具有相似的复杂性，只是每个内部调用本质上是恒定时间，因为它们只是增量。

假设他们一个接一个地跑，整个事情就是O(max^2 + max^2 + max^2) = O(max^2)。

这个答案更详细地说明了它：嵌套for循环的时间复杂度

推荐阅读