文章/答案/技术大牛

发布

社区首页 >问答首页 >这个算法最坏的时间复杂度是多少？

问这个算法最坏的时间复杂度是多少？
EN

Stack Overflow用户

提问于 2014-08-29 16:17:46

回答 3查看 155关注 0票数 3

void intFunction (int n, int value)
{
     int b,c;
     for (int j = 4; j < n; j++) {
          for (int i = 0; i < j; i++) {
               b *= val;
               for (int k = 0; k < n; ++k)
                    c += b;
          }
     }
}

我刚学会了Big-O的概念。所以对于这段代码，据我所知，外部循环运行时间是n，第二个内部循环运行n(n+1)/2，内部循环运行n(n+1)/2。那么运行时间是O(N^5)？我说的对吗？

algorithm

data-structures

big-o

回答 3

Stack Overflow用户

发布于 2014-08-29 16:32:56

求解以下公式将给出准确的迭代次数(并推导出增长复杂性的顺序)：

Result 经验性验证！

票数 2

Stack Overflow用户

发布于 2014-08-29 16:33:30

外部循环：

for (int j = 4; j < n; j++)

迭代n - 4次，所以它是O(n)。内部循环：

for (int i = 0; i < j; i++)

最多迭代n - 5次，所以这也是O(n)。最内层的那个：

for (int k = 0; k < n; ++k)

迭代n次，使其为O(n)。最后的复杂性是O(n * n * n) = O(n^3)。

票数 2

Stack Overflow用户

发布于 2014-08-29 16:36:51

让我们用迭代的次数来验证时间复杂度！

第一个循环->

for (int j = 4; j < n; j++){...}  // it will iterate for n-4 times.

第二个循环->

for (int i = 0; i < j; i++){...}  //it'll iterate for j-1 times for each iteration of outer loop started by j. See,this is dependent on First Loop(the outermost loop)...

第三个循环->

for (int k = 0; k < n; ++k){...}  //it'll always run n times independent to any previous-iteration whenever it is executed

因此，案例的总体迭代将是(在一个简单得多的版本中)：

(n-4)*(j-1)*n times.

但是，j本身从4变化到n-1。所以，j有点依赖于n，也就是4<=j<=n-1。//因此，这里j将迭代n-5次...

确切的治疗方法是这样的：

n*n-5*n=n^3-5*n^2.

它等于O(n^3)。

因此，在最坏的情况下分析，迭代的次数将是n^3-5*n^2，它的时间复杂度将是O(n^3)。

票数 1

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

原文链接：

https://stackoverflow.com/questions/25564284

复制

相似问题

问这个算法最坏的时间复杂度是多少？
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问这个算法最坏的时间复杂度是多少？EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问这个算法最坏的时间复杂度是多少？
EN