Не понимаю сложность времени по отношению к входному размеру этого модульного алгоритма возведения в степень
Вот псевдокод ниже:
pow2(a,b,k)
d := a, e := b, s := 1
until e = 0
if e is odd s:=s·d modk
d:=d2 modk
e := ⌊e/2⌋
return s
end
- Время выполнения цикла: log b(основание 2), так как это число раз, когда b = e может быть уменьшено вдвое, прежде чем оно будет округлено до 0
- Размер ввода b является log b
- Со всей этой информацией, приведенной выше, мои расчеты для сложности времени выглядят следующим образом: O(log(log b)) (основание 2) Что при упрощении похоже на O(2^b) Я знаю, что я неверен, так как этот алгоритм должен быть эффективный и поэтому сложность времени должна быть лучше.
- Фактическая временная сложность этого алгоритма составляет O(n) относительно входного размера b.
- пожалуйста, объясните, как сложность времени O(n) может быть определена из всей информации выше.