Сложность времени рекурсивной функции с двумя вызовами

Рассмотрим этот код:

def count_7(lst): if len(lst) == 1: if lst[0] == 7: return 1 else: return 0 return count_7(lst[:len(lst)//2]) + count_7(lst[len(lst)//2:]) 

Примечание: операции разреза будут рассматриваться как O (1).

Итак, мое inutation говорит мне, что это O (n * logn), но я изо всех сил пытаюсь доказать это с научной точки зрения.
Радуйтесь за помощь!

    Хорошо, математически (вроде;) Я получаю что-то вроде этого:

     T(n) = 2T(n/2) + c T(1) = 1 

    Обобщая уравнение:

     T(n) = 2^k * T(n/2^k) + (2^k - 1) * c T(1) = 1 

    n/2^k == 1 когда k == logN так:

     T(n) = 2^logN * T(1) + (2^logN - 1) * c 

    так как T(1) = 1 и применяя логарифмические свойства

     T(n) = n * 1 + (n-1) * c T(n) = n + n * c T(n) = n * (1+c) T(n) = O(n) 

    Подсказка, что это не O(n*logn) заключается в том, что вам не нужно комбинировать две подзадачи. В отличие от mergesort , где вам нужно объединить два подматрицы, этот алгоритм не должен ничего делать с рекурсивным результатом, поэтому его время может быть выражено как константа c .

    ОБНОВЛЕНИЕ: Интуиция за

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

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

    Путь от начала первой проблемы до тех пор, пока проблемы N размера 1 не будут логарифмическими, потому что на каждом шаге вы подразделяете на две части. Но на каждом шаге вы ничего не делаете с результатом, поэтому это не добавляет никакой сложности времени в решение.

    Надеюсь это поможет

    Самый простой способ – считать n кратным 2 для простоты: n = 2 m

    Сложность времени вашего алгоритма (c – постоянная):

     t(n) = 2 t(n/2) + c 

    И используя рекурсию, вы получаете:

    t(n) = 2 2 t(n/2 2 ) + 2c + c

    ...

    = 2 log(n) t(n/2 log(n) ) + c(2 log(n)-1 + ... + 2 2 + 2 1 + 2 0 )

    Который можно упростить, заметив, что log(n) = m , и, следовательно, 2 log(n) = 2 m = n .

    = n + c(2 log(n)-1 + ... + 2 2 + 2 1 + 2 0 )

    Наконец, приведенная выше сумма может быть сведена к 2 log(n) (что равно n )

      t(n) = (1 + c) n 

    Таким образом, ваше решение – O (n)

    Вы просматриваете весь элемент списка один раз, это O (n). Единственное отличие от простого рекурсивного сканирования – это порядок, в котором вы их сканируете. Вы делаете 1, n / 2, 2, 3 / 4n и т. Д. Вместо 1,2,3 …. но сложность такая же.