Может ли кто-то рассчитать сложность времени в большой О записи

Question

Может кто-нибудь помочь мне объяснить большую сложность этого алгоритма? Я пытался в течение часа, но я не понимаю сложности рекурсии. Я знаю, что первые 3 утверждения - это O (1), и я подумал, что под ними были O (n / 2) и O (n / 2), поэтому вместе O (n), но я не уверен.

def sum(a):
    if len ( a ) == 0:
        return 0
    elif len ( a ) == 1:
        return a [0]
    m = len (a )//2

    b = sum (a [: m ])
    c = sum (a [ m :])

    return b + c

Answer 1

В соответствии с документацией сложности времени Python , нарезка списка - это O(k), где k - длина среза.

Функция вызывает себя рекурсивно на двух срезах, каждый с размером n / 2 (игнорируя одно за другим из-за целочисленного округления). Соотношение рекуррентности таково:

T(n) = 2 T(n / 2) + O(n)

... где O(n) происходит от двух операций нарезки a[:m] и a[m:].

В соответствии с основной теоремой это O(n log n).

---

Чтобы сделать алгоритм O(n) таким, каким он должен быть, можно передать индексы подмассива вместо прямой нарезки массива или использовать тип массива numpy.

Answer 2

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

Чтобы сделать вывод, сложность по времени равна O(n), линейной по длине списка.

Вы можете попытаться определить рекуррентное отношение, чтобы доказать это формально.

Примечание
Вопрос может быть сложным из-за операции среза, используемой на каждой итерации. Это зависит от деталей реализации (для python это выглядит как O(k) с k длиной списка, но для numpy это должно быть O(1), как указано в комментариях) и может быть легко заменено передачей индексов (например, начало, конец), а не нарезанный список.
Здесь я предполагаю, что операция занимает постоянное время .