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

Question

Что значит доказать верхнюю или нижнюю границу алгоритма?

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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