питон

Question

Я следующий код, который я должен вычислить «Big-O» от:

def f3(lst): 
    i = len(lst) 
    while i>0: 
     for j in range(i): 
      for k in range(j, 10**5): 
       print(i) 
     i -= 2 

Предполагая, что lst список с длиной п, и операции принимают O(1), вот что я придумал to: 2-й for является постоянным, так как он повторяется до 10 ** 5 каждый раз, поэтому мы можем «игнорировать» его (это как O(1)).

В то время как выполняется n раз, а первая для цикла работает n/2 раза, поэтому в целом сложность должна быть O(n^2).

Верно ли это? Мой друг считает, что это O(n^4).

Спасибо.

Answer 1

Вы правильно установили, что цикл while повторяется n/2 раз. Внешняя петля for, содержащаяся внутри, выполнена для j = 1, 2, ... i, где i установлено в len(lst), len(lst) - 2, ..., 1 в последующих while итерациях. Таким образом, внешний цикл for выполнен для j = 1, 2, ..., len(lst), j = 1, 2, ..., len(lst) - 2, ..., j = 1. В общей сложности это O(n^2) итерации внешнего цикла for. В то время как внутренний цикл for не выполняется постоянным числом раз, он повторяет не более 10**5 раз, что равно константа. Поэтому O(n^2) является правильной верхней границей выполнения этой функции.

---

Вот несколько иное объяснение. Я надеюсь, вы согласитесь, что следующий код эквивалентен кода с точки зрения времени вычислений:

def f3_simple(n): 
    i = n       
    condition = i>0    
    while condition:    
     r1 = range(i)    
     for j in r1:    
      r2 = range(j, 10**5) 
      for k in r2:   
       print(i)   
     i -= 2      
     condition = i>0   

Вот тот же код с аннотациями:

def f3_simple(n): 
    i = n       # "length": O(1) 
    condition = i>0    # comparison: O(1) 
    while condition:    # executed O(n) times per function call 
     r1 = range(i)    # range(i): O(i) 
     for j in r1:    # executed O(n) times per WHILE iteration 
      r2 = range(j, 10**5)  # range(j, 10**5): O(10**5 - j) = O(1) 
      for k in r2:    # executed O(1) times per OUTER FOR iteration 
       print(i)    # print: O(1) 
     i -= 2      # decrement: O(1) 
     condition = i>0    # comparison: O(1) 

Таким образом, общее время выполнения действительно O(n^2).

Answer 2

Не ответ O (n^3)? Поскольку внутренний цикл все еще принимает время выполнения для проверки условия для него линейной функции j с определенного места, поэтому сумма j через i равна n, которая равна O (n^3)?