Анализ алгоритма время выполнения итеративного для петель

Question

Если я следующий код

def func(A,n): 
    for i in A-1: 
     for k in A-1: 
      for l in A-1 
       if A[i]+A[k]+A[l] = 0: 
        return True 
       else: 
        return False 

Как я проанализировать время выполнения этого алгоритма? Как я вижу, каждый цикл имеет 2 единицы, и каждый цикл работает n + 1 раз. цикл if затем запускает 3 * n раз, с 3 единицами. Тогда каждое возвращение будет одним, однако только из них будет работать, поэтому в итоге это будет примерно

T (n) = 2 (n + 1) +2 (n + 1) +2 (n + 1) +3 (n) +1 = 9n + 7

Является ли моя логика правильной или мне что-то не хватает. Также может ли время выполнения варьироваться от языка к языку?

Answer 1

Как сказано в комментариях, код как есть сейчас O (1), так как он будет выходить из func после одного прохода каждый раз.

Если вы изменили возврат к чему-то другому, например, задав переменную, то она станет O (n^3).

Чтобы объяснить, как вы получите это значение, я собираюсь свести задачу к двум петлям:

def func(A,n): 
    for i in A-1: 
     for k in A-1: 
     # Do Something else 

Если вы думаете о том, что это делает, для каждого значения i мы перебираем, мы выполним A-1 раз, чтобы пройти цикл k.

i=0, k=0 
i=0, k=1 
... 
i=0, k = A-1 

Так это продолжается A-1 или n циклов. Затем

i=1, k=0 
i=1, k=1 
... 
i=1, k=A-1 

Это также идет для n циклов. См. Шаблон? Для каждого значения i мы будем перебирать n раз. Теперь это будет продолжаться до тех пор, пока мы не исчерпаем все значения i, которые, как мы знаем, также являются A-1 или n раз. Таким образом, время выполнения для этой функции будет O (n^2).

В худшем случае время выполнения (большой-O) не будет сильно отличаться от языка программирования на языке программирования. Конечно, каждый язык программирования имеет разные уровни оптимизации и будет выполняться в разные промежутки времени, но, строго учитывая алгоритмические циклы, они будут одинаковыми.