Верхняя граница, нижняя граница

Ответ 1

Доказательство верхней границы означает, что вы доказали, что алгоритм будет использовать не более чем ограничение на ресурсе.

Доказательство нижней границы означает, что вы доказали, что алгоритм будет использовать не менее определенного предела для ресурса.

"Ресурс" в этом контексте может быть временем, памятью, пропускной способностью или чем-то еще.

Ответ 2

Верхняя и нижняя границы связаны с минимальной и максимальной "сложностью" алгоритма (я использую это слово, потому что он имеет очень специфическое значение в анализе сложности).

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

В особенно плохом случае, когда данные сортируются в соответствии с порядком, который вы хотите, время будет равно f (n ²). Это связано с тем, что каждый проход перемещает один элемент в нужное положение, и вам нужно n pass, чтобы сделать все элементы.

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

Как и в сторону, сортировка пузыря сильно клевещена (как правило, по уважительным причинам), но она может иметь смысл при определенных обстоятельствах. Я фактически использую его в приложении, где основная часть данных уже отсортирована, и только один или два элемента, как правило, добавляются за один раз до конца списка. Для добавления одного элемента и сортировки пузырьков с обратным направлением вы можете гарантировать, что новый список будет отсортирован за один проход. Это иллюстрирует концепцию нижней границы.

Фактически, вы могли бы оптимизировать сортировку пузырьков, которая устанавливает нижнюю границу для f (1), просто предоставив дополнительную привязку, которая указывает, отсортирован ли список. Вы должны установить это после сортировки и очистить его при добавлении элемента в конец.

Ответ 3

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

Я понимаю, что проблемы имеют нижнюю границу. Например, мы говорим, что нижняя граница сортировки на основе сравнения -\Omega (n log n); мы не делаем никаких предположений о том, какой конкретный алгоритм сортировки используется на основе сравнения. Независимо от алгоритма (сортировка слияния, быстрая сортировка и т.д.), Мы не можем сделать лучше этой границы \Omega (n log n). Нижние оценки говорят нам, интуитивно, насколько сложна конкретная проблема.

Когда мы говорим о конкретном алгоритме , мы говорим о верхних границах. Например, мы говорим, что верхняя граница сортировки пузырьков равна O (n ^ 2), а верхняя граница сортировки слияния - O (n log n). Наверху, интуитивно, расскажите, насколько хорош какой-то конкретный алгоритм при решении проблемы.