开发者

I need help for Calculating "Big O"

the first problem;

sum = 0;

for i = 1 to n; i++
 {   
 for j = 1 to i * i; j++
    {
    for k = 1 to j; k++
       sum ++;
    }
 }

and the

Second problem;

sum = 0;

for i = 1 to n
  {  
  for j = 1 to i * i
    {
    if j mod i == 0
      {  
      for k = 1 to j
           sum ++;
      }
    }
  }

Hi I am new in IT and I need a help (actually two :D )

I met with "big o" few days before and while I was studying about it I found this address, and actualy I learn manythings from here...

but most of the examples about "big o" were just for explaining it, here I have two questions. After my calculations I found the big o for the first one as O(n^5) and for the second one O(n^3). but these values were too huge...

therefore I am here, I need your help... (even you can write what ever the result is without exp开发者_JAVA技巧lanation but please help me about these questions)

Thanks as advance...


Okay, the definition of big-O is that a function g(x) is O(f(x)) if g(x)kf(x) for some constant k.

In other words, big-O tells you some idea of how fast a function grows; if it's $O(n)* it grows proportional to the length of the input. What you're counting, and details of the computation, are hidden in the constant.

Here's some examples:

for i from 1 to n {
  do something 
}

is O(n). You go through the n items once each.

for i from 1 to n {
}
for i from 1 to n {
}

twice in sequence is still O(n), because you're looking at each of the n items twice. That's 2n which is still O(n).

On the other hand,

for i from 1 to n {
   for j from 1 to n {

   }
 }

is O(n2) because for each step of i, you go through 1-n for j.

Straighten out the indentation of your code so we're sure what you're doing, and see if those examples help.

Update

These are pretty amusing questions, come to think of it.

  • the i*i term

Consider what the values of i*i, ie, i2 will be. At worst, i==n and so j is 1,4,9,16...(n*n). What's the sum of x2 for x from 1 to n? (Hint: 1/6(...)(...), now you fill in the blanks.)

  • the if ... mod term

when will that term be true?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜