Geek asks and answers

Computational complexity of the algorithm 1 2 4 8

I need to calculate the complexity of this algorithm:

f=1;
x=2;

for(int i=1;i<=n;i*=2)
   for(int j=1;j<=i*i;j++)   
      if(j%i==0)
         for(int k=1;k<=j*i;k++)
             f=x*f;

I figured out the pattern and the summation of the inner loop, which is equal to i ^ 2 (i (i + 1) / 2) but I can’t get the summation of this picture from the series (1 2 4 8 16 ...)

So how can I find the summation of this series?

+3
source share
2 answers

I am not going to solve this for you (it looks like homework). But here is a hint to simplify the problem.

This code:

for(int j=1; j<=i*i; j++)   
    if(j%i==0)
        // ... blah ...

equivalent to this code:

for(int j=i; j<=i*i; j += i)
    // ... blah ...
+3
source

Another tip for the outside for(int i=1;i<=n;i*=2): after each execution of the loop body, forI multiply by 2:

1 · 2 · 2 · ... · 2

And this is repeated as long as the condition is true:

1 · 2 · 2 · ... · 2 ≤ n

2s :

2 · 2 ·... · 2 = 2 x ≤ n

, 2, i. . x, logarithm 2, i. . < > 2 > ():

2 x ≤ n

x = log 2 (n) :

2 log 2 (n)= n

, for - (log 2 (n)) times true, Ο (log (n)), Ω (log (n)) , , θ ( ()).

0

More articles:


All Articles