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

go评论43阅读模式

What will be the time complexity of this algorithm

# 问题

``````我对竞技编程和大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");
}
}
}

``````

I am very new to competitive programming and to Big O notation.

``````public void function(int n){
for(int i = n; i &gt; 0; i/=3){
for(int j = 0; j &lt; i; j++){
System.out.println(&quot;Hello&quot;);
}
}
}
``````

This is the algorithm.
As far as i know about time complexity.It defines how run time gets affected from number of inputs.

So here if we take a example
if 'n' is 10.
The outer loop runs log n times and the inner loop runs 'i' times.

the inner loop runs relatively to 'i' not 'n'.
So im a bit confused here as to how the time complexity is calculated.
I think it is O(log n).Please correct me if i am wrong.

Will it be O(log n) or O (n log n) or (n^2).
Thank you.

# 答案1

n + n/3 + n/9 + n/27 + .... n/(3^log(n))

I will try to explain it in the simplest term possible

The outer loop will simply run log(n) with base 3 times.

Since, i is decreasing by factor of 3 every time. The total work done is equal to :

n + n/3 + n/9 + n/27 + .... n/(3^log(n))

since, n/3 + ... + n/(3^log(n)) will always be less than n

for e.g. let n = 100
then, 100 + 100/3 + 100/9 + 100/27 + ... = 100 + (33.3 + 11.11 + 3.7 + ...)

we can clearly see the terms in the bracket will always be less than 100

The total time complexity of the overall solution will be O(n).

# 答案2

Actually it will never terminate cause `i=0` and update is `i *= 3` so `i` will stay `0` so we can say `O(+oo)`

assuming you meant `for(int i =1...` instead, then its `O(n)`:

• Outer loop is clearly `O(log_3 n)` cause we keep multiplying by 3
• Inner loop will get executed `O(log_3 n)` times with iteration count of `(1 + 3 + 9 + 27 + ... + 3^log_3(n))` which is clearly a geometric progression, solving which gives us approx `3^log_3(n))` which according to log rules gives `n` so this loop takes `O(n)` for all iterations, so total complexity is `O(n)`

Actually it will never terminate cause `i=0` and update is `i *= 3` so `i` will stay `0` so we can say `O(+oo)`

assuming you meant `for(int i =1...` instead, then its `O(n)`:

• Outer loop is clearly `O(log_3 n)` cause we keep multiplying by 3
• Inner loop will get executed `O(log_3 n)` times with iteration count of `(1 + 3 + 9 + 27 + ... + 3^log_3(n))` which is clearly a geometric progression, solving which gives us approx `3^log_3(n))` which according to log rules gives `n` so this loop takes `O(n)` for all iterations, so total complexity is `O(n)`

# 答案3

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

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

``````for(int i = n; i &gt; 0; i/=3){
for(int j = 0; j &lt; i; j++){
System.out.println(&quot;Hello&quot;);
}
``````

}

Inner loop variable j is dependent on outer loop variable i, so your inner loop will be the one which will decide the complexity for your algorithm.
since j will run 'n' times in first run, 'n/3' times in second run and so on.. therefore your total complexity can be calculated as

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

resulting in O(n)

# 答案4

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

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

So this is a great question! It's a tricky one that takes a little more thinking to analyse.

As correctly stated in some of the other answers, the outer loop:

``````for(int i = n; i &gt; 0; i/=3)
``````

Will run log(n) times. Specifically log_3(n) times but in big O notation we don't often worry about the base so log(n) will be fine.

Now the nested loop is a bit trickier:

``````for(int j = 0; j &lt; i; j++){
``````

On first glance you may think this is a simple log(n) loop but lets look a little further.
So on the first iteration this will run N times since the value of i will be n. Next iteration it will be run n/3 times. Then n/9, n/27, n/81 etc....

If we sum this series, it is clear to see it will total less than 2n.
Therefore we can conclude this algorithm has a complexity of O(n).

# 答案5

``````for (int i=0; i &lt; n; i*=3) {
for (int j=0; j &lt; i; j++) {
System.out.println(&quot;Hello&quot;);
}
}
``````

``````O(log_3(n)^2)
``````

``````for (int i=0; i &lt; n; i*=3) {
for (int j=0; j &lt; i; j++) {
System.out.println(&quot;Hello&quot;);
}
}
``````

The outer loop in `i` is `O(log_3(n))`, because each increment of the loop decreases the amount of ground needed for `i` to reach `n` by a factor of 3. This is logarithmic behavior (`log_3` in this case). The inner loop in `j` simply iterates the same number of times as whatever the outer value of `i` might be, so we can just square the outer complexity, to arrive at:

``````O(log_3(n)^2)
``````

• 本文由 发表于 2020年8月3日 17:53:18
• 转载请务必保留本文链接：https://go.coder-hub.com/63227254.html
• algorithm
• big-o
• java

go 43

go 32

go 29

go 30