Рекуррентное отношение для цикла - PullRequest
Новая
       77

Рекуррентное отношение для цикла

1 голос
/ 20 октября 2010

Вопрос состоит в том, чтобы установить рекуррентное отношение, чтобы найти значение, заданное алгоритмом. Ответ должен быть в терминах teta (). 

foo = 0;

for int i=1 to n do
    for j=ceiling(sqrt(i)) to n do
        for k=1 to ceiling(log(i+j)) do
             foo++

1 Ответ

0 голосов
/ 20 октября 2010

Не совсем уверен, но здесь идет.

Второй цикл выполняется 1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5 раз => O(n^2) раз.См. здесь для обсуждения того, что sqrt(1) + ... + sqrt(n) = O(n^1.5).

Мы установили, что третий цикл будет запущен O(n^2) раз.Таким образом, алгоритм асимптотически эквивалентен примерно так: 

for i = 1 to n do
    for j = 1 to n do
        for k = 1 to log(i+j) do
            ++foo

Это приводит к сумме log(1+1) + log(1+2) + ... + log(1+n) + ... + log(n+n).log(1+1) + log(1+2) + ... + log(1+n) = log(2*3*...*(n+1)) = O(n log n).Это умножается на n, что приводит к O(n^2 log n).

Так что ваш алгоритм также O(n^2 log n), а также Theta(n^2 log n), если я не ошибаюсь.

...