Big-O анализ алгоритма

Question

Вопросы: alt text http://img12.imageshack.us/img12/2706/image2ot.jpg

Что я сделал: alt text http://img29.imageshack.us/img29/9192/image3sc.jpg

Но у меня нет абсолютно ни малейшего представления, разницу между 3.5 и 3.6.

Answer 1

Если вы немного более осторожны в своем решении 3.5, разница будет немного яснее. Ваша первая линия

T(n) <= n/4 (lg n)/4 + 3n/4 (3 lg n)/4 + n 

не совсем прав. Прежде всего, индуктивное предположение, что существует постоянная C такая, что

T(n) <= C n log n 

, так что вы, вероятно, должны держать эту C вокруг. Во-вторых, вы пропускаете шаг, на котором вы удаляете функцию пола. То, что вы на самом деле знаю, (не обращая внимания на постоянную C для простоты) является

T(n) <= floor(n/4) lg (floor(n/4)) + floor(3n/4) lg (floor(3n/4)) + n 

Так как же вы заботитесь о пол? Хорошо, floor(x) <= x; но как насчет lg(floor(x)) (который появляется дважды)? Ключом здесь является то, что lg является функцией увеличения, поэтому lg(floor(x)) <= lg(x) также. Так

T(n) <= n/4 lg(n/4) + 3n/4 lg(3n/4) + n 

Теперь очистить его с некоторыми свойствами логарифмов (вы будет необходимость использовать эту подсказку о lg 3) и закончить шаг индукции.

ОК, так зная, что в чем разница с 3,6? Ну, теперь у вас есть функция потолка вместо функции пола, поэтому вы не можете просто игнорировать ее. Но

ceiling(x) <= x + 1 

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

Answer 2

Разница между 3.5 и 3.6 - это функции потолка и пола в T (n/4). Кроме того, они идентичны. И насколько я могу сказать, разница не имеет значения для вычислений для O (T (n)), как вы можете видеть из ожидаемых результатов.

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