python - 我如何证明和分析代码的运行时间，是 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

这是它的分割:

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)