Сколько раз будет выполняться этот цикл?

Question

Я беру курс алгоритмов, и мне сложно определить, сколько раз будет выполняться следующий цикл. Я думаю, что ответ - log (n) (из-за середины = i/2), но мне трудно убедить себя. Любая помощь или советы по выяснению, сколько раз этот цикл будет проходить, будет отличным. Благодаря!

def loop(arr): 

    i = len(arr) - 1 
    mid = i/2 

    while i > 0: 
     i = mid - 1 
     mid = (i)/2 

Answer 1

Вы, по сути, выполняете двоичный поиск без части поиска. У вас есть пространство, и вы продолжаете делиться им пополам, пока не закончите.

Это O (log (n)).

http://bigocheatsheet.com/

На стороне записки, это может быть полезно запустить алгоритм для различных входов для I, и построить график выполнения как функции I. Возможно, вы захотите вставить постоянную задержку для каждой итерации (например, sleep (50) или так), потому что цикл будет работать очень быстро.