Как узнать время выполнения конкретной процедуры?

Для каждой из приведенных ниже процедур пусть T (n) будет временем выполнения. Найти порядок T (n) (т.е. найти f(n) такое, что T (n) ∈ (f(n)).

Процедура Fum(int n):

for i from 1 to n do    
 y ← 1/i
 x ← i
 while x > 0 do    
  x ← x − y 
 end while
end for

Я знаю, как найти время выполнения простых функций, но поскольку это вложенный цикл, в котором внутренний цикл зависит от переменной из внешнего цикла, у меня возникают проблемы.


runtime algorithm time-complexity big-o procedure
person user2264035    schedule 23.01.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

В данном случае это должно быть 1+4+9+...+n^2 = n(n+1)(2n+1)/6 или просто O(n^3).

Для каждого шага в цикле for он будет выполняться i^2 раз для while. Учитывая x=i;y=1/i;, потребуется i^2 (как x=y*i^2) раз, чтобы x достигло x<=0 на шаге уменьшения x=x-y.

За i будет 1,2,...,n, суммируя их, получится 1+4+9+...n^2 = n(n+1)(2n+1)/6.

person herohuyongtao    schedule 23.01.2014
comment
Спасибо, не могли бы вы рассказать мне, как вы пришли к такому ответу? - person user2264035; 23.01.2014

arrow_upward
0
arrow_downward

Во-первых, давайте рассмотрим время выполнения внутреннего цикла: мы хотим выяснить, сколько раз выполняется внутренний цикл с точки зрения i. То есть мы хотим найти f(i) в x-f(i)y = 0. Если мы подставим x = i и y = 1/i, мы получим f(i) = i^2.

Мы знаем, что внешний цикл будет выполняться ровно n раз, поэтому мы получаем общее количество запусков внутреннего цикла:

= 1 + 4 + 9 + ... + n^2

Эта сумма равна n(n+1)(2n+1)/6, что составляет O(n^3)

person gms7777    schedule 23.01.2014
comment
Нет, 1+4+9+... = n(n+1)(2n+1)/6, не n^2. - person herohuyongtao; 23.01.2014