这个算法的时间复杂度是多少

Question

我对竞争性编程和大O符号非常陌生

public void function(int n){
   for(int i = n; i > 0; i/=3){
       for(int j = 0; j < i; j++){
           System.out.println("Hello");
       }
   }
}

这就是算法。 据我所知，关于时间复杂性。它定义了运行时如何受到输入数量的影响

这里我们举个例子 如果n是10。 外循环运行logn次，内循环运行'i'次

内部循环相对于“i”而不是“n”运行。 所以我在这里有点困惑，时间复杂度是如何计算的。 我想是O（对数n）。如果我错了，请纠正我

它是O（logn）还是O（logn）或（n^2）。 请帮我解决这个问题。 多谢各位

Answer 1

对于您的代码：

for(int i = n; i > 0; i/=3){
   for(int j = 0; j < i; j++){
       System.out.println("Hello");
   }

}

内循环变量j依赖于外循环变量i，因此内循环将决定算法的复杂性。 因为j在第一次跑步时跑n次，在第二次跑步时跑n/3次，以此类推。。因此，您的总复杂性可以计算为

n+n/3+n/9+n/27+

导致O（n）

Answer 2

实际上它永远不会终止，因为i=0而更新是i *= 3，所以i将保持0，所以我们可以说O(+oo)

假设你的意思是for(int i =1...，那么它的O(n)：

• 外环显然是O(log_3 n)，因为我们一直在乘以3
• 内部循环将被执行O(log_3 n)次，迭代次数为(1 + 3 + 9 + 27 + ... + 3^log_3(n))，这显然是一个几何级数，求解它会给出大约3^log_3(n))，根据日志规则，它给出n，所以这个循环对所有迭代都需要O(n)，所以总复杂度为O(n)

Answer 3

我会尽量用最简单的术语来解释

外部循环将简单地以3次为基数运行log（n）

因为，我每次都减少3倍。完成的总工作量等于：

n+n/3+n/9+n/27+。。。。n/（3^log（n））

因为，n/3+…+n/（3^log（n））将始终小于n

例如，设n=100 然后，100+100/3+100/9+100/27+…=100 + (33.3 + 11.11 + 3.7 + ...)

我们可以清楚地看到括号中的术语总是小于100

整体解决方案的总时间复杂度为O（n）

Answer 4

在代码片段中：

for (int i=0; i < n; i*=3) { 
    for (int j=0; j < i; j++) {
        System.out.println("Hello");
    }
}

在i中的外环路是O(log_3(n))，因为环路的每个增量都会将i到达n所需的地面数量减少3倍。这是对数行为（在本例中为log_3）。j中的内部循环只需重复与i的外部值相同的次数，因此我们可以将外部复杂度平方，从而得出：

O(log_3(n)^2)

Answer 5

所以这是一个很好的问题！这是一个需要更多思考才能分析的棘手问题

正如在其他一些答案中正确指出的，外环：

for(int i = n; i > 0; i/=3)

将运行日志（n）次。具体地说，log_3（n）次，但在大O表示法中，我们通常不担心基数，所以log（n）就可以了

现在嵌套循环有点棘手：

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

乍一看，您可能认为这是一个简单的日志（n）循环，但让我们再看一看。 因此，在第一次迭代中，它将运行N次，因为i的值将为N。下一次迭代将运行N/3次。然后n/9，n/27，n/81等等

如果我们把这个系列加起来，很明显它的总数将小于2n。 因此，我们可以得出这样的结论：该算法的复杂度为O（n）