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

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");
       }
   }
}

这就是算法。据我所知，时间 complexity.It 定义了运行时间如何受到输入数量的影响。

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

内循环运行相对于 'i' 而不是 'n'。所以我在这里对如何计算时间复杂度有点困惑。我认为是O(log n)。如果我错了请指正。

会是 O(log n) 还是 O (n log n) 还是 (n^2)。这个你能帮我吗。谢谢。

Answer 1

在您的代码片段中：

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 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

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

外循环将简单地运行 log(n) 以 3 为底数。

因为，i 每次都减少 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 = 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 5

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

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

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

将运行 log(n) 次。具体来说 log_3(n) 次，但在大 O 表示法中，我们不经常担心基数，所以 log(n) 就可以了。

现在嵌套循环有点棘手：

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

乍一看，您可能认为这是一个简单的 log(n) 循环，但让我们进一步看一下。因此，在第一次迭代中，这将运行 N 次，因为 i 的值将为 n。下一次迭代将是运行 n/3 次。然后 n/9、n/27、n/81 等....

如果我们对这个系列求和，很明显它的总数将少于 2n。因此我们可以得出结论，该算法的复杂度为 O(n)。

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

What will be the time complexity of this algorithm

java

algorithm

big-o