Какова была бы сложность p = B^E?

Question

Вот мое решение р = B^E

p,b,e:= 1,B,E 
    WHILE e!=0 DO 
    IF e is EVEN THEN 
    b:= b^2 
    e:= e/2 
    ELSE 
    p:= p*b 
    e:= e-1 
    FI 
OD. 

Сейчас, на мой взгляд, цикл выполняется E раз и сложность журнала п. Я прав?

Вот как я бы объяснить сложность:

Пояснение: В худшем случае цикл будет выполняться раз E, но для каждого четного числа встречаются, е уменьшается вдвое 2, исключая фактор элементов из расчета , следовательно, размер вычисления не будет расти экспоненциально, когда размер ввода будет расти. Поэтому сложность алгоритма O (log (E)).

Пример: положим E = 10 Тогда мы будем иметь шаги расчета, как показано ниже: 1. б: = Ь^2 и е = 10/2 = 5 2. р = р * (Ь^2) и e = 5-1 = 4 3. b = b^4 и e = 4/2 = 2 3. b = b^8 и e = 1 4. p = p * b^10 и e = 0

Давайте увеличим е до 100. Тогда мы будем иметь:

1. б: = Ь^2 и е = 100/2 = 50
2. Ь: = Ь 4 и е = 25
3. р: = р * Ь 4 и е = 24
4. Ь: = Ь^8 и е = 12
5. Ь: = Ь^16 и е = 6
6. Ь: = Ь^32 и е = 3
7. р: = р * Ь^36 и е = 2
8. Ь: = Ь * Ь^32 и е = 1
9. б: = p * b^34 и e = 0 Отсюда видно, что увеличение размера E от 10 до 100, которое в десять раз не увеличивает число итераций только на 5. Следовательно, оказывается, что сложность O (log E)

Answer 1

Сложность: O(logE).

Обратите внимание, что не может быть два ELSE состояние один за другим, так что в худшем случае, так в большинстве после двух итераций, e будет уменьшена наполовину, пока она не станет 0.

Это означает, что вы будете нуждаться в большинстве 2*log_2(E) итераций, что на самом деле в O(logE)

---

Обратите внимание, что это не включает в себя aritmetics возведения в квадрат b снова и снова, что может добавить еще один фактор в уравнении, так как, когда вы закончите , b будет в O((B^2)^logE) = O(B^(2logE)), который может не быть O(1) для расчета, в зависимости от архитектуры и фактических размеров B,E.