Как этот алгоритм O (n)?

Question

Проработки рецидивов, вы можете получить, что при каждом вызове этой функции, временная сложность будет: T(n) = 2T(n/2) + O(1)

и высоту дерева рекуррентного будет log2(n), где общее количество вызовов (то есть узлы в дереве).

Инструктор сказал, что эта функция имеет временную сложность O (n), но я просто не могу понять, почему.

Далее, когда вы заменить O (N) в сложности уравнения времени есть странные результаты. Например,

Т (п) < = сп

Т (п/2) < = (сп)/2

Назад в исходное уравнение:

Т (п) < = сп + 1

Где это, очевидно, не соответствует действительности, потому что cn + 1 !< cn

Answer 1

Ваш инструктор правильно. Это приложение Master theorem.

Вы не можете заменить O (n) так же, как вы это делали в уравнении временной сложности, правильная подстановка была бы полиномиальной формой, подобной a + b, поскольку O (n) показывает только самую высокую значительную степень (может быть константы меньшей степени).

Чтобы расширить ответ, вы правильно распознаете уравнение сложности времени формы T(n) = aT(n/b) + f(n), с асимметрией a = 2, b = 2 и f (n). равна O (1). С этим типом уравнений вы имеете три случая, которые зависят от сравниваемого значения log_b (a) (стоимость рекурсии) и f (n) (стоимость решения основной задачи длины n): 1 ° f (n) намного длиннее самой рекурсии (log_b (a) < f (n)), например a = 2, b = 2 и f (n). равна O (n^16). Тогда рекурсия ничтожно малой сложности, а общая временная сложность может быть приравнена к сложности F (N):

T(n) = f(n) 

2 ° Рекурсия длиннее, чем F (п) (log_b (а)> F (n)), что здесь имеет место. Тогда сложность O (log_b (a)) в вашем примере O (log_2 (2)), то есть O (n).

3 ° Критический случай, когда f (n) == log_b (a), т. Е. Существует k> = 0 такое, что f (n) = O (n^{log_b (a)} log^k (n)), то сложность составляет:

T(n) = O(n^{log_b(a)} log^k+1 (a)} 

Это уродливый случай, на мой взгляд.