Время выполнения тета-нотации - PullRequest
Новая
       19

Время выполнения тета-нотации

0 голосов
/ 06 сентября 2018

Посмотрев на код: 

for(i=n-1; i>=0; i-=2)
   for(j=15; j<100; j+=3)
      sum +=i+j

Я бы сказал, что время выполнения для этого в терминах тэта-нотации должно быть Θ (n ^ 2), так как есть два цикла и const (i и j). Это будет правильно?

1 Ответ

0 голосов
/ 06 сентября 2018

Я вставлю другой штекер для этой старой асимптотической максимы

«Если сомневаешься, работай наизнанку!»

Давайте еще раз посмотрим на этот код: 

for(i=n-1; i>=0; i-=2)
   for(j=15; j<100; j+=3)
      sum +=i+j;

Давайте начнем с самого внутреннего утверждения, которое добавляет в переменную sum. Время выполнения этого оператора не зависит ни от каких других переменных здесь, поэтому оно работает (1). Итак, давайте перепишем код так: 

for(i=n-1; i>=0; i-=2)
   for(j=15; j<100; j+=3)
      do Theta(1) work

Теперь давайте посмотрим на этот внутренний цикл for. Обратите внимание, что этот цикл всегда выполняется одинаковое количество раз (около 30 единиц), независимо от значений других переменных. Это означает, что этот цикл выполняется постоянное количество раз и выполняет постоянный объем работы, и, таким образом, общий эффект этого цикла заключается в выполнении & Theta; (1) работы. Это показано здесь: 

for(i=n-1; i>=0; i-=2)
    do Theta(1) work

Так что теперь мы оставили этот последний цикл. Здесь мы видим, что проделанная работа напрямую и линейно зависит от n. В частности, этот цикл выполняет (The) (n) итераций и (1) работает за одну итерацию, поэтому общая выполненная работа составляет & Theta; (n) .

Обратите внимание, что это не число для циклов, которое определяет время выполнения, а , что делают эти циклы. Подсчет количества циклов - хороший способ получить приблизительный оцените время выполнения, но более точный подход, проиллюстрированный мною выше для работы изнутри наружу.

...