Определите временную сложность моего алгоритма с кодом python - PullRequest
Новая
       12

Определите временную сложность моего алгоритма с кодом python

0 голосов
/ 18 апреля 2020

мое задание просит меня придумать алгоритм и проанализировать временную сложность моего алгоритма. Следующий код - это то, что я написал с python. a - любое заданное значение, а b установлено как значение по умолчанию 1. Цель состоит в том, чтобы найти минимальные шаги, чтобы a = b удвоилось или увеличило b на 1 (b + 1). Если мой алгоритм верен, то время, когда l oop для my принимает l (logn), равно как и для l oop, так что в последний раз сложность моего алгоритма равна O (logn)? Спасибо! 

a = 17
b = 1
count = []
while a !=1 :
    if a % 2 == 0:
        count.append(2)
        a = a/2
    else:
        count.append(1)
        a -= 1
count.reverse()
for i in count:
    if i == 2:
        b = 2*b
    else:
        b += 1
...