Сложность времени с циклами

Question

Я не уверен, если я понимаю вычисления временной сложности. Мне даны эти петли, и это мои расчеты. Тем не менее, я не уверен, что сказать о больших O здесь.

Цикл 1:

lst = []     
i=1       
while i<n: 
    lst = list(range(i))  
    i *= 2 

Я полагаю, что каждая операция занимает O (1) времени. В этом цикле 1-я строка и вторая строка выполняются 1 раз каждый. Первая строка цикла while содержит 3 операции - диапазон, список и присвоение этого значения lst. Поскольку мы имеем дело с диапазоном, я предполагаю, что он работает n + 1 раз.

Последняя строка цикла имеет 2 операции: умножение на 2 и присвоение этого значения i, и выполняется n раз.

Из этого, я думаю, что общее количество будет: 1 + 1 + 3 (n + 1) + 2n = 5n + 5.

Поскольку это линейная функция, то большой O будет O (n)?

===============

Цикл 2:

lst = []    
i=1     
while i<n: 
    lst = lst + [i]  
    i *= 2  

Здесь мы имеем подобный случай, однако первая строка из цикла в то время как имеется 2 операции. Затем
1 + 1 + 2n + 2n = 4n + 2.

Поскольку это линейная функция, это также O (n)?

========================== Loop 3:

lst = []   
i=1     
while i<n: 
    lst += [i]   
    i *= 2 

Я думаю, что LST + = [я] будет выполняться 2 операции в 2 раза, так как это расчет на месте? Я не уверен в этом. Если это правильно, то общая сумма будет 6n + 2

Вопросы: я исчисляю эти права или я совершенно не прав? Как написать большие O для каждого из этих циклов?

Answer 1

LOOP 1: О (п § п)

Цикл работает log2 (N) раз, его среднее O (журнал N). каждая итерация делает (в худшем случае) n действий. поэтому сложность O (n log n).

LOOP 2: O (журнал N)

Цикл работает log2 (N) раз, его среднее O (журнал N). Я полагаю, что присвоение lst = lst + [i] просто добавляет узел (и не создает новый список). его среднее значение O (1), поэтому сложность O (log n). Если я ошибаюсь, задание создает новый список, поэтому каждая итерация выполняет (в худшем случае) n действий. поэтому сложность О (п § п)

LOOP 3: O (журнал N)

Как и в контуре 2. Здесь, назначение О (1) точно, не предположение. ..