Big O анализ нотации с использованием рекурсией дереву

Question

проблемой с: http://qpleple.com/divide-and-conquer/ Сравнения алгоритмов

Вы менеджер на Facebook и три инженера из вашей команды придумал эти три алгоритма для обнаружения поддельной Facebook счетов в список n = 1 миллиарда учетных записей Facebook.

Rakesh решает проблемы, деля их на пять подзадач в два раза меньше, рекурсивное решение каждой подзадачи, а затем объединение решений в линейное время.

Крис решает проблемы размера n путем рекурсивного решения двух подзадач размера n-1 и последующего объединения решений в постоянное время.

Матус решает задачу размера п деления их на девять подзадач размера n/3, рекурсивно решением каждой подзадачи, а затем объединяя решения в O(n²) времени

Таким образом, с помощью Master теоремы я выяснил, что:

• алгоритм Ракеша имеет время работы O(nlog₂(5))
• алгоритма Матуса имеет запущенное время O(n2log(n))

растягивая рекурсивное дерево и с помощью:

алгоритм Rasket имеет:

 
#levels = log₂(n) 
#of nodes at level k = 5k 
overhead per node at level k = n/2k 

Но независимо от того, как сильно я стараюсь, я не могу получить суммированием сравняться O(nlog₂(5)) , и то же самое касается алгоритма Матуса.

Кроме того, есть ли способ решить время работы алгоритма Криса с помощью основной теоремы?

Answer 1

Применение

 
#levels = log₂(n) 
#of nodes at level k = 5k 
overhead per node at level k = n/2k 

в

Вы получаете (используя geometric formula)

 
T(n) = Σk=0,...,log₂(n) 5k ⋅ n/2k 
    = n ⋅ Σk=0,...,log₂(n) (5/2)k 
    = n ⋅ (1 - (5/2)log₂(n)+1)/(1 - 5/2) 
    = (n - n ⋅ (5/2) ⋅ 5log₂(n)/2log₂(n))/(1 - 5/2) 
    = (n - n ⋅ (5/2) ⋅ 5log₂(n)/n)/(1 - 5/2) 
    = (n - (5/2) ⋅ 5log₂(n))/(1 - 5/2) 
    = ((5/2) ⋅ 5log₂(n) - n)/(5/2 - 1) 
    = ((5/2) ⋅ 5log₂(n) - n)/(3/2) 
    = (5/3) ⋅ 5log₂(n) - (2/3) ⋅ n    ∈ Θ(5log₂(n)) 

Теперь осталось только показать 5log₂(n) = nlog₂(5), что может быть сделано примерно в одной строке.

Рецидив уравнение, я получаю для Криса, это

T(n) = 2⋅T(n-1) + O(1) 

Это не разрешимы с помощью теоремы мастер, но вы можете просто расширить его на сумму и решить:

 
T(n) = 2⋅T(n-1) + Θ(1) 
    = 2⋅(2⋅T(n-2)+ Θ(1)) + Θ(1) 
    = 2²⋅T(n-2) + 2⋅Θ(1) + Θ(1) 
    ... 
    = 2n⋅T(1) + 2n-1⋅Θ(1) + ... + 2⋅Θ(1) + Θ(1) 
    = 2n+1⋅Θ(1) - 1   ∈ Θ(2n) 

Это относится к T(1) ∈ Θ(1).