Какова временная сложность следующего сегмента кода? - PullRequest
Новая
       6

Какова временная сложность следующего сегмента кода?

0 голосов
/ 06 января 2019

Мне нужна помощь, чтобы определить, какова временная сложность сегмента кода.

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

sum = 0; count = 0;
for (int i = 1; i < N; i = i*2){
    sum = sum + 1;
    for (int j = i; j < N*N; j = j*2){
        count++;
    }
    for (int k = i; k < N; k++){
        count--;
    }
}

Я предполагаю, что это: (logN * logN) + (logN * N) -> O (NlogN) Но поскольку третий цикл не вложен во второй цикл, я не уверен, как правильно определить сложность. Поэтому, пожалуйста, помогите мне .. :)

1 Ответ

0 голосов
/ 07 января 2019

Предположим сначала N=2^M. Тогда M = lg(N).

Внешний цикл работает на i = 2^0, 2^1, 2^2, ..., 2^(M-1). Всего M шагов.

Первый внутренний цикл работает для j = 2^s, ..., 2^(M + M - 1) на шаге s (из M шагов). Итого 2M-s.

Второй выполняется для k = 2^s, 2^s + 1, ..., 2^M - 1 на шаге s. Итого 2^M - 2^s.

Первый цикл занимает всего (2M-0) + (2M-1) + ... + (2M - (M-1)), что составляет O(M^2) = O(lg(N)^2).

Второй (2^M-2^0) + ... + (2^M-2^(M-1)), что равно M2^M - 2^M + 1, что составляет O(M2^M) = O(Nlg(N)).

Следовательно, общая сложность составляет O(lg(N)lg(N)) + O(Nlg(N)) = O(Nlg(N)).

Для общего случая, когда N не является степенью двойки, рассмотрим M таким, что 2^M < N < 2^(M+1) и заключим, что сложность остается O(Nlg(N)).

...