首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >嵌套的同时循环大O。估计值

嵌套的同时循环大O。估计值
EN

Stack Overflow用户
提问于 2020-01-23 07:20:15
回答 2查看 91关注 0票数 1
代码语言:javascript
运行
复制
int i = 0;
int n = 20;

while (i < n)
{
  i++;
  int j = i;

  while (i < n)
  {
    printf("this is %d", i);
    i++;
  }

  i = j;
}

因此,为了估计这个函数的时间复杂度,我估计的方法是外循环运行n时间。内环运行n - 1时间吗?那么这个嵌套循环的时间复杂度是O(n^2)吗?

EN

回答 2

Stack Overflow用户

发布于 2020-01-23 07:28:49

您可以重写初始代码。

代码语言:javascript
运行
复制
int n = 20;
int i = 0;

while (i < n) 
{
  i++;
  int j = i;

  while (i < n) 
  {
    printf("this is %d",i);

    i++;
  }

  i = j;
}

与其相当:

代码语言:javascript
运行
复制
int n = 20;

for (int i = 1; i < n; ++i) 
  for (int j = i; j < n; ++j)
    printf("this is %d", j); 

现在很明显,您有O(n**2)时间复杂性:

代码语言:javascript
运行
复制
(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n * (n - 1) / 2

操作(printf(...))和

代码语言:javascript
运行
复制
O(n * (n - 1) / 2) = O(n**2 / 2 - n / 2) = O(n**2)
票数 1
EN

Stack Overflow用户

发布于 2020-01-23 07:30:49

在以后的迭代中,内循环运行次数与n-1、n-2、n-3、.= 1.所以和n(n-1)/2,从而导致了与O(n^2)一样的渐近时间复杂度.

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/59873362

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档