Как найти время выполнения указанного ниже алгоритма?

Question

Предположим, что время работы модуля A является константой M, а N - размером входных данных.

1. Set J:=N.
2. Repeat Steps 3 and 4 while J>1.
3.   Module A.
4.   Set J:=J/2.
     [End of Step 2 loop.]
5. Return.

Answer 1

Учитывая, что деление числа на два может быть выполнено в постоянное время, временная сложность этого алгоритма составляет O (log N) . Однако для (очень) больших чисел деление на два требует некоторого дополнительного времени: O (log K) с K значением, которое нужно разделить.

Алгоритм останавливается, когда J меньше или равно единице. Таким образом, это означает, что если J=2, то потребуется M + 1 шагов (время оценивает модуль и один, чтобы разделить J на два, давайте здесь предположим, что деление на два требует постоянной время).

Теперь для J=2*K (с K переменной) снова требуется M + 1 шагов, чтобы завершить цикл, плюс время, которое требуется с J=K для решения проблемы.

Значит, мы получаем следующее уравнение:

T(1) = 0
T(N) = T(N/2) + M + 1

Таким образом, мы видим, что объем работы растет линейно в количестве итераций , а количество итераций имеет верхний предел log ₂ N : если мы должны выполнить K шагов, тогда начальный N находится между 2 ^K-1 + 1 и 2 ^K .

Таким образом, это означает, что общее количество шагов ограничено:

T(N) = (M+1) * log2(N)

M является константой, что означает, что M+1 является константой, следовательно, часть variable равна log2(N). Это O (log N) .

Строго говоря, однако, если N может быть очень большим, так что нам нужно произвольное количество памяти, то деление не является постоянным. Если мы используем двоичную систему счисления, мы можем сдвинуть биты в O (log K) на K число, чтобы разделить на два (и log ₂ k количество бит).

В этом случае шаг, таким образом, принимает:

T(1) = 0
T(N) = T(N/2) + M + log2(N)

При K итерациях количество шагов ограничено:

 K
---
\
/    log2(I) + M
---
I=1

Сумма log ₂ (i) с i от 1 до k равна log ₂ (k!) с верхним пределом O (k log k) . Поскольку число шагов k ограничено O (log N) , это, таким образом, означает, что общая временная сложность делений составляет O (log N & times; log (журнал N)) . Общая временная сложность всех вызовов к модулю остается O (M & times; log N) , поэтому O (log N) , поэтому временная сложность составляет O (log N & times ; (1 + log (log N))) , или проще O (log N + log N & times; log (log N)) .

Однако возможно немного изменить алгоритм так, чтобы нам не приходилось выполнять эти деления явно : мы можем использовать некоторый вид курсора, который каждый раз перемещается на один шаг дальше, пока N «исчерпан», и в этом случае временная сложность снова равна O (log N) .

Answer 2

TL; DR

Временная сложность этого алгоритма в O (log (n))

Объяснение

• Поскольку Модуль A работает в постоянное время M, можно сказать, что его время работы составляет O (1)
• То же самое касается инструкции Set J:=J/2, она работает в O (1)
• Предположим, что цикл в строке 2 выполняется K раз. Таким образом, после того, как цикл завершил итерацию K раз, мы получим J = 1 .
  • После 1-й итерации цикла у нас осталось N / 2 итераций. После 2-го у нас N / 4 . 3-й N / 8 , 4-й N / 16 и т. Д.
  • После K итераций (когда цикл завершен итерацией) мы получим J = 1 = N / (2 ^ K) .
  • Итак N / (2 ^ K) = 1 , что дает нам N = 2 ^ K . Следовательно, число итераций равно K = log2 (N)
• Инструкции на каждой итерации цикла принимают O (1) , в итоге получается O (log (N))

Примечания

• Вот статья , которая иллюстрирует концепцию, используя ее в Алгоритм двоичного поиска