Мне нужна помощь для расчета "Big O" - PullRequest
Новая
       2

Мне нужна помощь для расчета "Big O"

2 голосов
/ 26 марта 2011

первая проблема; 

sum = 0;

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

и

Вторая проблема; 

sum = 0;

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

Привет, я новичок в ИТ и мне нужна помощь (на самом деле два: D)

Я встретился с "big o" несколько дней назад, и пока я изучал его, я нашел этот адрес, и на самом деле я узнаю здесь много всего ...

, но большинствопримеры о "большом o" были только для объяснения этого, здесь у меня есть два вопроса.После моих расчетов я нашел большой o для первого как O (n ^ 5), а для второго O (n ^ 3).но эти значения были слишком велики ...

поэтому я здесь, мне нужна ваша помощь ... (даже вы можете написать любой результат без объяснения причин, но, пожалуйста, помогите мне с этими вопросами)

Спасибо, как заранее ...

1 Ответ

2 голосов
/ 26 марта 2011

Хорошо, определение big-O состоит в том, что функция g (x) равна O (f (x)) , если g (x) ≤ kf (x) для некоторой константы k .

Другими словами, big-O дает вам некоторое представление о том, как быстро растет функция;если это $ O (n) *, оно увеличивается пропорционально длине ввода.То, что вы рассчитываете, и детали вычислений скрыты в константе.

Вот несколько примеров: 

for i from 1 to n {
  do something 
}

равно O (n) .Вы просматриваете n пунктов по одному разу. 

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

дважды в последовательности по-прежнему O (n) , потому что вы смотрите на каждый из n предметов дважды.Это 2n , что по-прежнему O (n) .

С другой стороны, 

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

   }
 }

равно O (n 2 ) потому что для каждого шага i вы проходите через 1-n для j .

Уточните отступ кода, чтобы мы были уверены, что вы делаете, и посмотрите, помогут ли эти примеры.

Обновление

Это довольно забавные вопросы, если подумать.

  • член i*i

Рассмотрим, каковы будут значения i*i, т. Е. I 2 .В худшем случае, i == n и, следовательно, j равно 1,4,9,16...(n*n).Какова сумма х 2 для х от 1 до n?(Подсказка: 1/6 (...) (...), теперь вы заполняете пробелы.)

  • мод if ...

когда этот термин будет правдой?

...