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

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。外循环运行 log n 次，内循环运行 'i' 次。

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

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

Answer 1

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

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

因为，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)。