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++;
}
}
}
解决方案
你有三个循环。让我们拿第一个。
外部循环运行max
时间,每次通过该循环都运行内部循环max
时间,总共max * max
调用a[i][j]= rand()%2;
。每次调用都会生成一个随机数:我不知道这样做的成本是多少,但它独立于max
. 这个循环的成本是O(max^2)
。
其他两个循环具有相似的复杂性,只是每个内部调用本质上是恒定时间,因为它们只是增量。
假设他们一个接一个地跑,整个事情就是O(max^2 + max^2 + max^2) = O(max^2)
。
这个答案更详细地说明了它:嵌套for循环的时间复杂度
推荐阅读
- python - 如何在 discord.py 中创建 discord.Permissions 对象?
- python - 物体中心到图像中心的距离
- c# - 将列表框的所有项目发送到列表视图的第一列。但是listview是另一种形式
- tcp - 无法使用 Fluentd @tcp 捕获 syslog 客户端 IP 地址
带有警告的参数“source_address_key” 未使用 - php - 如何在 PHP 中将多个变量传入和传出回调函数?
- excel - Excel计算行数,同时将合并的行视为一个
- python-3.x - 如何使用 python 在 telnet 会话中发出命令
- unix - Unix命令按顺序检查丢失的文件
- android - 无法导入 android.support.v7.widget.Toolbar
- python - 服务退出并出现异常代码:PyInstaller 文件中的 255