Как я могу обосновать и проанализировать время выполнения кода, это O (n)?

Question

Как я могу обосновать и проанализировать время выполнения кода с помощью рекурсивного вызова, это O (n)?

A = [10,8,7,6,5]
def Algorithm(A):
  ai = max(A)             # find largest integer
  i = A.index(ai)
  A[i] = 0
  aj = max(A)             # finding second largest integer 

  A[i] = abs(ai - aj)     # update A[i]
  j = A.index(aj)
  A[j] = 0                # replace the A[j] by 0
  if aj == 0:             # if second largest item equals
    return ai       # to zero return the largest integer
 return Algorithm(A)     # call Algorithm(A) with updated A

Answer 1

Сначала я немного скептически относился к тому, работает ли ваш алгоритм в O (n). Также следующая программа

import timeit, random
import matplotlib.pyplot as plt

code = """
def Algorithm(A):
    ai = max(A)             # find largest integer
    i = A.index(ai)
    A[i] = 0
    aj = max(A)             # finding second largest integer 

    A[i] = abs(ai - aj)     # update A[i]
    j = A.index(aj)
    A[j] = 0                # replace the A[j] by 0
    if aj == 0:             # if second largest item equals
        return ai       # to zero return the largest integer
    return Algorithm(A)     # call Algorithm(A) with updated A
Algorithm(%s)
"""

x, y = [], []
lst = [random.randint(-1000, 10000)]
for i in range(1000):
    lst.append(random.randint(-1000, 10000))
    time = timeit.timeit(stmt=code % lst, number=10)
    x.append(i)
    y.append(time)

plt.plot(x, y)
plt.show()

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

явно поддерживает нелинейный рост. Сказано иначе, поскольку алгоритм имеет сложность O (n ^ 2), поэтому невозможно доказать, что он работает в пределах O (n).

Answer 2

Вот его разбивка:

def Algorithm(A):
    ai = max(A)             # O(n)
    i = A.index(ai)         # O(n)
    A[i] = 0                # O(1)
    aj = max(A)             # O(n)

    A[i] = abs(ai - aj)     # O(1)
    j = A.index(aj)         # O(n)
    A[j] = 0                # O(1)
    if aj == 0:             # O(1)
        return ai           # O(1)
   return Algorithm(A)      # recursive call, called up to n times recursively

Последний рекурсивный вызов вызывается до тех пор, пока max(A) не равно 0, что в n раз, в худшем случае, если всеположительны.

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