Когда возникают потоки и потолки при решении рецидивов?

Я сталкивался с местами, где полы и потолки игнорируются при решении повторений.

Пример из CLRS (глава 4, стр. 83), где пренебрегают полом:

enter image description here

Здесь (стр .2, упражнение 4.1-1) - пример, где потолок игнорируется: (EDIT: Я считаю, что это несколько подозрительно.)

enter image description here

Фактически в CLRS (стр .88) упоминалось, что:

"Полы и потолки НЕПОСРЕДСТВЕННО не имеют значения при решении рецидивов"

Мои вопросы:

  • Здесь "обычно" означает ВСЕ случаи? Если да, я могу просто забыть их все время.
  • Если нет, то , когда полы и потолки действительно учитываются при решении повторений?

Примечание. Это не проблема домашних заданий. Я думал об этом, пока я обновлял свои концепции DS и algo.

Ответы

Ответ 1

Функции пола и потолка удовлетворяют следующим неравенствам для всех x:

  • x & minus; 1 < & Lfloor; <я > х & rfloor; & Ле; <Я > х

  • x & le; & Lceil; <я > х & rceil; < <Я > х + 1

Таким образом, в первом примере мы имеем: n/2 & rfloor; & Ле; n/2. Кроме того, поскольку логарифм является монотонно возрастающей функцией, мы знаем, что lg & lloor; n/2 & rfloor; & Ле; lg ( n/2). Поставив их вместе, получим первое неравенство 2 ( c & llolo; n/2 & rfloor; lg & llolo; n/2 & rfloor;) + n & le; cn lg ( n/2) + n.

Второй пример фактически содержит ошибку: c lg & lceil; n/2 & rceil; + 1 никогда не меньше, но может быть равно c lg (n/2) + 1. Однако верно, что c lg & lceil; n/2 & rceil; + 1 & le; c lg ( n/2 + 1) + 1, которую мы можем тогда связать сверху, например, c lg ( n/2) + 2 (предполагая, что n & ge; 2) и, следовательно, получаем желаемый вывод, что T ( n) &в; O (lg n).

Фактически, второй пример содержит и другие ошибки: даже с предположениями, изложенными в следующем абзаце (который вы не указали), знак last = должен быть & le;.

(Ps. Phew, это была настоящая боль, чтобы набрать без LaTeX. Что, если ничего другого, почему такие вопросы лучше задавать на math.SE.)

Ответ 2

Оба ваших примера поддаются анализу по основной теореме. теорема Акра-Бацци обобщает основную теорему и дает достаточное условие, когда небольшие возмущения можно пренебречь (возмущение h (x) есть O ( x/log 2 x)). Для целых индексированных рекуррент, анализируемых Akra-Bazzi, вы можете игнорировать пол и потолок всегда, так как их возмущения не более 1.

Каждое повторение, не охватываемое Akra-Bazzi, довольно экзотично в контексте алгоритмов и структур данных.