Какова асимптотика c времени выполнения этого псевдокода? - PullRequest
Новая
       6

Какова асимптотика c времени выполнения этого псевдокода?

1 голос
/ 17 января 2020

В следующем фрагменте кода f() - любая функция, для которой требуется время Θ (1). Сложность времени должна быть Θ (n 4/3 ), может кто-нибудь объяснить, почему? 

for(int i = 1; i ≤ n; i = 2∗i) {
    for(int j = 1; j∗j∗j ≤ n; j = j+1) { 
        for(int k = 1; k ≤ i∗i; k = k + i) {
            f();
        }
    }
}

По моему анализу первое for l oop занимает Θ (журнал 2 n) времени, второе for l oop равно Θ (n 1/3 ), а третье for l oop равно Θ (i) , Таким образом, в итоге мы имеем Θ ((log 2 n) × n 1/3 × i).

Поскольку я могу быть n, мы имеем Θ (( log 2 n) × n 1/3 × n) = Θ (n 4/3 log 2 n). Где моя ошибка?

1 Ответ

1 голос
/ 08 марта 2020

Ваша граница не жесткая, потому что вы посчитали i как Θ (n), но i в среднем не Θ (n). Рассмотрим последовательность значений, которые принимает i, и сложим их, чтобы подсчитать общее количество итераций для внутреннего l oop. Мы можем пока игнорировать середину l oop над j, поскольку она не зависит от i и k.

Последовательность значений для i равна 1, 2, 4, 8, ... до п. Если мы скажем, что n = 2 r для некоторого r, это прогрессия геометрии c с суммой 2 r + 1 - 1, которая примерно вдвое больше, чем n, поэтому это Θ (н). Это учитывает как внешний, так и внутренний цикл; середина l oop дает другой коэффициент of (n 1/3 ), и, следовательно, общая сложность составляет Θ (n 4/3 ), как требуется.

...