Верхняя граница против нижней границы для наихудшего случая времени работы алгоритма
Я учусь об анализе алгоритмов. Я понимаю концепцию времени выполнения алгоритма в худшем случае.
Однако каковы верхние и нижние границы времени выполнения алгоритма в худшем случае?
Что может быть примером, когда верхняя граница для времени выполнения наихудшего случая алгоритма отличается от нижней границы для времени выполнения наихудшего случая того же алгоритма?
3 ответа
Для функции f(n), g(n) верхняя граница ( большой O), если для "достаточно большого п", f(n)<=c*g(n)для постоянного c, [г доминирует f]
g (n) - нижняя граница ( большая Омега), если для "достаточно большого n", f(n) >= c*g(n)для постоянного c, [е доминирует над г]
Если g(n) верхняя граница и нижняя граница f(n) [с разными c] мы говорим, что g (n) является жесткой границей для f(n) [Большая тета]
Используйте пример для верхней границы вместо жесткой: иногда бывает трудно найти жесткую границу, например, для рекурсивного алгоритма Фибоначчи. поэтому мы легко находим верхнюю границу O(2^n). больше информации можно найти в ответах на этот пост.
Сначала поговорим о случаях. Случай ввода для алгоритма связан с примером проблемы. Для задачи сортировки (где мы хотим найти перестановку множества в определенном порядке), я могу посмотреть на экземпляр, подобный набору чисел {1, 5, 4, 2, 6}. Этот набор чисел будет входом в алгоритм сортировки, который предназначен для решения проблемы сортировки, такой как Выбор сортировки или один из других алгоритмов сортировки.
Те же самые наборы входных данных могут быть даны любому алгоритму, который хочет решить проблему. Неважно, какой алгоритм сортировки я использую, набор входных данных всегда одинаков (потому что, по определению, они все являются экземплярами одной и той же проблемы). Тем не менее, данный случай может быть лучше или хуже для данного алгоритма. Некоторые алгоритмы всегда работают одинаково, независимо от того, какие входы, но некоторые алгоритмы могут работать хуже на некоторых входах. Тем не менее, это означает, что у каждого алгоритма есть лучший и худший случай; мы также иногда говорим о среднем случае (принимая среднее значение по всем случаям) или ожидаемом случае (когда у нас есть основания ожидать, что один случай будет более распространенным, чем другие).
Примеры случаев алгоритма
Проблема "найти минимум несортированного списка" всегда работает одинаково для каждого возможного ввода. Независимо от того, какой умный алгоритм вы пишете, вы должны проверять каждый элемент. Не имеет значения, есть ли у вас список нулей или список случайных чисел или список, где первый элемент является минимальным, вы не будете знать, пока не дойдете до конца. Все случаи одинаковы для этого алгоритма, поэтому лучший случай - это худший случай, а также средний случай и ожидаемый случай. Если бы список был отсортирован, мы могли бы сделать лучше, но это другая проблема.
Проблема "найти данный элемент в списке" другая. Предполагая, что вы использовали алгоритм, который выполняет линейный обход списка, может оказаться, что данный элемент был первым элементом списка, и вы сделали это немедленно. Тем не менее, это также может быть последним элементом списка, и в этом случае вам придется пройтись по всему объекту, прежде чем вы его найдете. Так что у вас был лучший случай и худший случай.
Алгоритмы как функции размера ввода
Когда мы хотим проанализировать алгоритм, мы, алгоритмы, думаем о каждом возможном случае, который мы могли бы бросить в алгоритм. Обычно два наиболее интересных случая - это лучший случай и худший случай. Если вы рассматриваете время выполнения алгоритмов как функцию его входа, лучшим вариантом является вход, который минимизирует функцию, а наихудшим случаем является вход, который максимизирует функцию. Я использую здесь "функцию" в математическом смысле алгебры: последовательность пар х / у (пары ввода / вывода или в данном случае "размер ввода / количество шагов выполнения"), которые рисуют линию.
Поскольку время выполнения алгоритма является функцией его входных данных, мы имеем различный лучший (и наихудший) случай для каждого возможного размера ввода. Поэтому иногда мы рассматриваем лучший случай как один вход, но это действительно набор входов (по одному на каждый размер ввода). Наилучший и наихудший случай - это очень конкретные вещи в отношении данного алгоритма.
Bounds
А как насчет границ? Границы - это функции, которые мы используем для сравнения с функцией данного алгоритма. Существует бесконечное число граничных функций, которые мы могли бы рассмотреть. Сколько возможных видов линий вы можете нарисовать на графике? Вот как много граничных функций. Большинство алгоритмов обычно интересуются только несколькими конкретными функциями: такими как постоянная функция, линейная функция, логартмическая функция, экспоненциальная функция и т. Д.
Верхняя граница - это функция, которая находится поверх другой функции. Нижняя граница - это функция, которая находится под другой функцией. Когда мы говорим о Big O и Big Omega, нам все равно, будут ли границы ВСЕГДА выше или ниже другой функции, просто после определенного момента они всегда (потому что иногда алгоритмы становятся странными для небольших входных размеров).
Существует бесконечное число возможных верхних границ для любой данной функции и бесконечное количество возможных нижних границ для любой данной функции. Но это один из тех странных моментов, когда мы говорим о разных размерах бесконечности. Чтобы быть верхней границей, функция не должна быть ниже другой функции, поэтому мы исключаем бесконечное число функций ниже другой функции (поэтому она меньше, чем набор всех возможных функций).
Конечно, только потому, что есть бесконечные верхние границы, не означает, что они все полезны. Функция f(∞) является верхней границей для каждой функции, но это все равно, что сказать: "У меня меньше бесконечного количества долларов" - не особенно полезно для выяснения, если я без гроша или миллионер. Поэтому нас часто интересует верхняя граница, которая является "жесткой" (также известной как "наименьшая верхняя граница" или "супремум"), для которой не существует лучшей верхней границы.
Лучший / худший случай + нижний / верхний предел
У нас есть лучшие / худшие случаи, которые представляют верхнюю и нижнюю функции функции времени выполнения алгоритма. У нас есть верхняя и нижняя границы, которые представляют другие функции, которые могут быть сверху или снизу (соответственно) любой другой функции. Они могут быть объединены, чтобы сформулировать ключевые идеи об алгоритмах.
В худшем случае нижняя граница: функция, которая является границей ниже функции времени выполнения алгоритма, когда этому алгоритму задаются входные данные, которые максимизируют время выполнения алгоритма.
В худшем случае верхняя граница: функция, которая является границей над функцией времени выполнения алгоритма, когда этому алгоритму задаются входные данные, которые максимизируют время выполнения алгоритма.
Нижний предел наилучшего случая: функция, которая является границей ниже функции времени выполнения алгоритма, когда этому алгоритму задаются входные данные, которые минимизируют время выполнения алгоритма.
Верхний предел в лучшем случае: функция, которая является границей над функцией времени выполнения алгоритма, когда этому алгоритму задаются входные данные, которые минимизируют время выполнения алгоритма.
Примеры границ случая
Давайте приведем конкретные примеры того, когда мы можем заботиться о каждом из них:
Нижний предел в худшем случае. Классическим примером здесь является сортировка на основе сравнения, которая, как известно, в худшем случае Ω(n log(n)). Независимо от того, какой алгоритм вы разработали, я могу выбрать набор входных данных для наихудшего случая, при этом самая жесткая функция нижней границы является логарифмической. Вы не можете создать алгоритм, который превосходит этот предел для наихудшего случая, и вам не стоит беспокоиться об этом. Это основа сортировки. Конечно, для худшего случая есть много нижних границ: постоянная, линейная и сублинейная - все нижние. Но они не являются полезными нижними границами, потому что там линейно-линейная нижняя граница является самой жесткой.
Оптимальный нижний предел: сортировка вставок работает, просматривая список и вставляя все вышедшие из строя последовательности в нужном месте. Если список отсортирован, ему нужно будет пройти по списку только один раз без каких-либо вставок. Это означает, что самая тесная нижняя граница наилучшего случая - это Ω(n). Вы не можете добиться большего, чем это, не жертвуя правильностью, потому что вам все еще нужно иметь возможность пройтись по списку (линейное время). Однако нижняя граница для лучшего случая лучше, чем нижняя граница для худшего случая!
Верхняя граница наихудшего случая: нам часто интересно найти жесткую верхнюю границу для наихудшего случая, потому что тогда мы знаем, насколько плохо наш алгоритм может работать в худшие времена. Наихудший случай сортировки вставки - это список, который совершенно не в порядке (т.е. полностью перевернут из своего правильного порядка). Каждый раз, когда мы видим новый элемент, мы должны перемещать его в начало списка, продвигая все последующие элементы вперед (что является линейной временной операцией, и выполнение этого линейного числа раз приводит к квадратичному поведению). Тем не менее, мы все еще знаем, что это поведение вставки будет O(n2) в худшем случае, действуя как жесткая верхняя граница для худшего случая. Это не очень хорошо, но лучше, чем верхняя граница, скажем, экспоненциальной или факторной! Конечно, это допустимые верхние границы для наихудшего случая, но, опять же, это не так полезно, как знать, что квадратичный является жесткой верхней границей.
Верхний предел в лучшем случае: что хуже всего может сделать наш алгоритм в лучшие времена? В примере перед нахождением элемента в списке, где первый элемент был нашим желаемым элементом, верхняя граница равна O(1). В худшем случае он был линейным, но в лучшем случае худшее, что может случиться, - это то, что он все еще постоянен. На мой взгляд, эта конкретная идея обычно не так важна, как верхняя граница наихудшего случая, потому что мы, как правило, больше заинтересованы в работе с наихудшим, а не с лучшим случаем.
Некоторые из этих примеров на самом деле Ө, а не просто O и Ω. В других случаях я мог бы выбрать нижнюю или верхнюю граничные функции, которые не были тесными, но все же были достаточно приблизительными, чтобы быть полезными (помните, если мы не стеснены, у меня есть бесконечный колодец, из которого можно извлечь!). Обратите внимание, что может быть трудно найти убедительные примеры различных комбинаций случай / связанный, потому что комбинации имеют различную полезность.
Заблуждения и терминология
Часто вы будете видеть людей с неправильными представлениями об этих определениях. Фактически, многие совершенно хорошие компьютерные ученые будут использовать эти термины свободно и взаимозаменяемо. Тем не менее, идея падежей и границ различна, и вы должны преуспеть, чтобы убедиться, что понимаете их. Значит ли это, что в вашей повседневной жизни возникнет разница? Нет. Но когда вы выбираете между несколькими различными алгоритмами, вы хотите прочитать мелкий шрифт о случаях и границах. Кто-то говорит вам, что их алгоритм имеет верхнюю границу наилучшего случая, равную O (1), вероятно, пытается стянуть шерсть с глаз - обязательно спросите их, какова верхняя граница худшего случая!
Позвольте мне проиллюстрировать это на примере:
Наихудшее время работы для быстрой сортировки Theta(n^2), Таким образом, действительная нижняя граница будет Omega(n) и верхняя граница будет O(n^3), Это говорит о том, что в худшем случае для быстрой сортировки потребуется как минимум линейное время, так и самое большее кубическое время.
Это не очень точное утверждение, но для более сложных алгоритмов такие заявления - лучшее, что мы можем сделать.