Как рассчитать сложность худшего случая для функции?

Question

def functionX(L): 
    """ L is a non-empty list of length len(L) = n. """ 
    i= 1 
    while i< len(L) -1: 
     j = i-1 
     while j <= i+ 1: 
      L[j] = L[j] + L[i] 
      j = j + 1 
     i= i+ 1 

Для j цикла почему у нас есть 3 итерации с 3 шагами вместо i итераций? Мне трудно понять это.

Answer 1

Вы имеете n итераций внешнего цикла, так и в каждой внешней петлевой итерации, 3 итераций внутреннего цикла, так как при данном i, переменная j имеет значение i - 1, i и i + 1. Поэтому сложность равна O(3 * n) = O(n).

Answer 2

Яснее ли для петель, чем в цикле?

def functionY(L): 
    N = len(L) 
    for i in range(1,N-1): 
     for j in range(i-1,i+2): 
      L[j] = L[j] + L[i] 

Как насчет псевдокода?

for i in range(N): # drop the -1s on both ends; O(n-2) = O(n) 
    for j in range(3): # (i-1) to (i+2) covers 3 elements 
     do something 

Это совершенно ясно, что ответ Тони правильный, мы находимся в классе O (n). В частности, к линии L[j] = L[j] + L[i] будет доступен 3n-6 раз. Это класс сложности O(3n) = O(n). Если вы ищете доступ к массиву как свою атомную операцию, то у нас есть O(3*(3n-6)) = O(n), все еще. Класс сложности не изменится, если строка будет читать L[j] += L[i], хотя общее количество обращений к массиву будет уменьшаться.