时间戳

首页 > 解决方案 > 使用 if 语句确定三个嵌套 for 循环的大 O

algorithm - 使用 if 语句确定三个嵌套 for 循环的大 O

问题描述

以下代码的大 O 是什么：

y=1;
x=3;

for(int i =1 ; i < =n ; i*=2)
   for(int j =1; j<= i * i; j++)
      if (i % j == 0)
         for(int k = 1; k<=j; k++) 
            y=y*x;

我的想法：看另一个类似的问题，我认为最里面的循环是O(n)，第一个循环是O(log (n))..至于中间O(n^2)

所以总体结果是O(log(n)*n^3)

我的回答和思路对吗？我是新手，所以我希望我能得到一些帮助来解释这个循环是如何工作的。

标签： algorithmtime-complexitybig-onested-loops

解决方案

如果 .最内层循环将运行j时间i % j == 0。由于中间循环会运行i^2多次，只有当j < i它可能满足指定条件时。因此，在i^2中间循环的迭代中，至少有i^2 - i几次条件不满足。

假设我们用 表示除数的数量i，tau(i)其中j < i只有条件满足的次数，这意味着最内层循环的总复杂度tau(i)最多等于除数之和（见这篇文章的证明）。i77/16 i

因此，中间循环与内循环的总复杂度最多为(i^2 - i) + (i - tau(i)) + 77/16 i = i^2 + 77/16 i - tau(i)。

我们也知道存在tau(i)（O(i^(1/loglog(i)))见这里的证明）。现在，要找出整个循环的复杂性，我们需要对最后一个表达式求和i = 1, 2, 4, ..., n。由于我们希望找到渐近复杂度并且我们在这里有一个和，我们可以忽略 的较低幂i。因此，整个循环的时间复杂度为（与因子为和项1 + 2^2 + (2^2)^2 + ... + (2^2)^log(n) = ((2^2)^(log(n)+1)-1)/(2^2-1) = Theta(n^2) 的几何和）。2^2log(n)

总而言之，指定代码的时间复杂度较高的分析Theta(n^2)也在其中O(n^2)。

推荐阅读