Верхняя и нижняя границы имеют отношение к минимальной и максимальной «сложности» алгоритма (я использую это слово заранее, поскольку оно имеет очень специфическое значение в анализе сложности).
Возьмите, к примеру, нашего старого друга, пузырьковую сортировку. В идеальном случае, когда все данные уже отсортированы, требуется время f (n), функция зависит от n, количества элементов в списке. Это потому, что вам нужно сделать только один проход набора данных (с нулевыми перестановками), чтобы убедиться, что ваш список отсортирован.
В особенно плохом случае, когда данные сортируются в порядке, обратном желаемому, требуемое время становится f (n 2 ). Это потому, что каждый проход перемещает один элемент в нужную позицию, и вам нужно n проходов, чтобы выполнить все элементы.
В этом случае верхняя и нижняя границы различаются, хотя сложность big-O остается прежней.
Кроме того, пузырьковая сортировка сильно порочна (обычно по уважительным причинам), но может иметь смысл в определенных обстоятельствах. Я на самом деле использую его в приложении, где большая часть данных уже отсортирована и только один или два элемента, как правило, добавляются за один раз в конец списка. Для добавления одного элемента и с пузырьковой сортировкой в обратном направлении вы можете гарантировать, что новый список будет отсортирован за один проход. Это иллюстрирует концепцию нижней границы.
Фактически, вы могли бы сделать оптимизацию пузырьковой сортировки, которая устанавливает нижнюю границу для f (1), просто предоставив дополнительную информацию, которая указывает, отсортирован ли список. Вы установите это после сортировки и очистите при добавлении элемента в конец.