Каково время работы этой программы? (если у нас есть цикл for, который находится внутри цикла while)

Question

def hsum(X):
    while len(X) > 1:
        Y=[None]*(len(X)//2)
        for i in range(0,len(X)//2):
            Y[i] =  X[2*i] + X[(2*i)+1]
        X=Y
    return X[0]

Здесь X - массив целых чисел, а длина X равна n = 2 ^ k. И длина уменьшается (как в n // 2) после того, как она входит в цикл while, и эта уменьшенная длина является диапазоном цикла for (например, n = 2 ^ 6 = 64, и когда она входит в цикл while, она уменьшается доn // 2, поэтому диапазон цикла for равен (0, 64/2 = 32). Итак, время выполнения цикла while равно O (log n), но каково будет время выполнения цикла for? И каково время выполнения всего кода в терминах Big-Oh?

Answer 1

Существует простой способ определить сложность большого алгоритма этого алгоритма. Операция + в строке 5 выполняется, по крайней мере, столько же раз, сколько в коде, поэтому если мы посчитаем, сколько раз выполнено +, то это будет такой же, как и сложность всего алгоритма. Это нормально, потому что все остальное является базовой операцией, кроме строки Y = [None] * len(X // 2), которая не имеет более высокой сложности, чем цикл с + in.

, поскольку алгоритм вычисляет сумму чиселв списке, и ничего не добавляется , кроме чисел из списка (или частичных сумм чисел из списка), в общей сложности сделано len(X) - 1 добавлений, и поэтому алгоритм O (*)1010 * n ) где n - длина списка ввода.

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