Когда полы и потолки имеют значение при решении повторений?

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

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

введите здесь описание изображения

Здесь (стр.2, упражнение 4.1– 1) — это пример, когда потолок игнорируется: (EDIT: я понял из общественного мнения, что это несколько подозрительно.)

введите здесь описание изображения

На самом деле в CLRS (стр.88 ) упоминается, что:

Полы и потолки ОБЫЧНО не имеют значения при решении повторений

Мои вопросы:

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

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


recurrence algorithm math asymptotic-complexity
person Tejas Patil    schedule 08.04.2012    source источник
comment
В ваших примерах этим не пренебрегают.   -  person Oliver Charlesworth    schedule 08.04.2012
comment
@ Оли Чарльзворт: да .. это то, что я видел до сих пор, но этим пренебрегали. Даже CLRS упоминает, что ОБЫЧНО игнорируется. Я хочу знать, когда пол и потолок действительно беспокоят? или я могу просто продолжать пренебрегать ими ВСЕ время?   -  person Tejas Patil    schedule 08.04.2012
comment
… кроме того, это вопрос по математике, а не по программированию. На первый взгляд, причина, по которой пол/потолки устраняются неравенством, заключается в том, что исследуются асимптотические поведения; рецидив вообще не решается.   -  person Potatoswatter    schedule 08.04.2012
comment
@Potatoswatter: я видел вопросы о повторениях, больших и т. Д. Алгоритмические материалы, публикуемые на SO, которые не были напрямую связаны с программированием. Если это не то место, чтобы опубликовать мой вопрос, не могли бы вы предложить хорошее место?   -  person Tejas Patil    schedule 08.04.2012
comment
@TejasP math.stackexchange.com   -  person Potatoswatter    schedule 08.04.2012

Ответы (2)


arrow_upward
11
arrow_downward

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

  • x1 ‹ x x

  • x x ‹ x+1

Таким образом, в первом примере мы имеем n / 2 n / 2. Кроме того, поскольку логарифм является монотонно возрастающей функцией, мы знаем, что lg n< /i> / 2 lg(n / 2). Сложив их вместе, мы получим первое неравенство 2(c n / 2 lg n / 2) + n cn lg(n / 2) + n.

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

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

(Ps. Уф, печатать без LaTeX было очень больно. Именно поэтому подобные вопросы лучше задавать на math.SE< /а>.)

person Ilmari Karonen    schedule 08.04.2012
comment
@ilmariKaronen: спасибо за объяснение. Могу ли я сказать, что потолки никогда нельзя игнорировать при использовании метода замещения? - person Tejas Patil; 08.04.2012
comment
@TejasP: для этажей f(⌊x⌋) ≤ f(x) для любой монотонно возрастающей функции f. Это не относится к потолкам, но вместо этого мы всегда можем использовать f(⌈x⌉) ≤ f(x+1). - person Ilmari Karonen; 08.04.2012
comment
@Ilmari Karonen 8 лет - это долго, но, тем не менее, вы можете объяснить, почему f(⌈x⌉) ≤ f(x+1) верно? Я имею в виду, что f(⌈x⌉) ‹ f(x+1) верно но как вы сказали, что ≤ верно - person lava_07; 21.07.2020
comment
@ lava_07: f(x) = 42 — монотонно возрастающая функция (хотя и не строго возрастающая). f(⌈x⌉) ‹ f(x+1) выполняется, если f строго возрастает, но f(⌈x⌉) = f(x+1) также возможно, если f оказывается постоянным в интервале от ⌈x⌉ до х+1. - person Ilmari Karonen; 21.07.2020
comment
В той же ноте журнал не строго увеличивается? например, если я считаю, что интервал между ⌈x⌉ и x+1 будет ли журнал когда-либо постоянным? если я не ошибаюсь, журнал также является функцией один к одному, которая, вероятно, исключает постоянные интервалы? (поправьте меня, если я ошибаюсь, я не совсем математик!) - person lava_07; 21.07.2020
comment
@ lava_07: Да, функция логарифма строго возрастает, по крайней мере, как определено математически. Внезапно я не уверен на 100%, что это все еще гарантированно сохраняется даже после учета неточности с плавающей запятой, но я подозреваю, что это не так. (Опять же, с плавающей запятой вы даже не можете гарантировать, что x+1 ≥ x.) - person Ilmari Karonen; 21.07.2020
comment
Итак, для верхней границы (c lg ⌈n / 2⌉ + 1) (c lg (n / 2 + 1) + 1) все еще действует? как в ‹ определенно верно, но с математической точки зрения для приведенного выше рекуррентного соотношения является ли верхняя граница его с ‹= действительным? (Не знаю, имеет ли это смысл!) - person lava_07; 21.07.2020
comment
@ lava_07: Ну, x ‹ y подразумевает x ≤ y, так что да. - person Ilmari Karonen; 22.07.2020

arrow_upward
5
arrow_downward

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

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

person oldboy    schedule 08.04.2012
comment
спасибо за указание на теорему Акра-Бацци. Я не знал этого раньше .... могу ли я сказать то же самое о методе подстановки (т.е. пол и потолки всегда игнорируются)? - person Tejas Patil; 08.04.2012
comment
Если ваше предположение для T монотонно возрастает и вас устраивает верхняя граница, то вы всегда можете игнорировать нижний предел. Чтобы формально иметь дело с потолком, обычно нужно анализировать T (ceil (...)) как T (...) + ..., где второй ... - член младшего порядка. Например, если вы предполагаете, что T(n) = n^2, то T(ceil(n/2)) ≤ T(n/2 + 1) = T(n/2) + n + 1. На самом деле, хотя , можно написать целую докторскую диссертацию по алгоритмам, не решая ни одного повторения с помощью метода подстановки. - person oldboy; 08.04.2012