Определение BigO рецидива

Question

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

Как бы я быстро определил BigO?

Answer 1

Я не совсем уверен, что такое dn, но при условии, что вы имеете в виду постоянную, умноженную на n:

Согласно Wolfram Alpha , решение уравнения рекуррентности для:

f(n) = f(n / 2) + cn

есть:

f(n) = 2c(n - 1) + c1

что бы сделать это O(n).

Answer 2

Используйте повторную обратную замену и найдите шаблон. Пример здесь .

Answer 3

Что ж, рекуррентная часть отношения - это часть T (n / 2), которая каждый раз вдвое уменьшает значение n.

Таким образом, вам потребуется прибл.(log2 n) шагов, чтобы добраться до условия завершения, следовательно, общая стоимость алгоритма составляет O (log2 n).Вы можете игнорировать часть dn, так как она является операцией с постоянным временем для каждого шага.

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

Answer 4

используйте теорему мастера см. http://en.wikipedia.org/wiki/Master_theorem

Кстати, асимптотическое поведение вашего рецидива равно O (n), если d положительно и достаточно меньше n (размер проблемы)