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

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

这是算法
就我所知时间复杂度定义了运行时间如何受输入数量的影响

所以在这里举个例子
如果'n'是10
外层循环运行log n次内层循环运行'i'

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

它会是O(log n)还是O(n log n)还是(n^2)
请帮我解答一下
谢谢
英文:

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).
Please help me out with this.
Thank you.

答案1

得分: 5

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

外部循环将简单地以以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)。

英文:

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

得分: 1

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

得分: 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)。

英文:

for your code :

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

得分: 1

这是一个很好的问题!这是一个有点需要更多思考才能分析的棘手问题。

如一些其他答案中正确说明的那样,外部循环:

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

英文:

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

得分: 0

在你的代码片段中:

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

外部循环中的 i 复杂度为 O(log_3(n)),因为每次循环增加一次,将 i 达到 n 需要的迭代次数会减少3的倍数。这是对数行为(在这种情况下是log_3)。内部循环中的 j 仅迭代与外部的 i 值相同的次数,因此我们可以将外部复杂度的平方,得到:

O(log_3(n)^2)
英文:

In your code snippet:

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)

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

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定