Верхние и нижние оценки в алгоритмах

Question

Я видел несколько статей, описывающих верхнюю границу как наихудший случай и нижнюю границу как наихудший случай. Между тем в некоторых статьях даны объяснения верхней / нижней границы наихудшего случая.

В общем, это заставило меня задать три вопроса:

1. Что такое верхние / нижние границы?
2. Как их можно определить отдельно в худшем случае?
3. Можно ли определить границы и для других случаев (лучший, средний)?

Answer 1

Что такое верхние / нижние границы?

Нас интересуют границы функций, как вы можете прочитать в Википедии.

Кроме того, часть этого ответа упоминает:

Для функции f(n), g(n) верхняя граница ( большой O), если для "достаточно большого п", f(n)<=c*g(n)для постоянного c, [г доминирует f]
g (n) - нижняя граница ( большая Омега), если для "достаточно большого n", f(n) >= c*g(n)для постоянного c, [е доминирует над г]

Как их можно определить отдельно в худшем случае?

Они либо будут разными, либо одинаковыми; в этом случае мы говорим Θ(n), где n, как правило, размер проблемы. Как сказал Герцог:

В худшем случае наилучший и средний случаи могут быть представлены как функция (для завершающих алгоритмов). Каждая из этих функций имеет верхнюю и нижнюю границы (которых бесконечно много). Выполнение постоянного числа операций для элемента (например, лучший случай для сортировки вставки и средний / худший случай для линейного поиска) будет иметь жесткую границу (нижнюю и верхнюю границу), равную Θ(n), но также верхнюю границу O (n²) или нижняя граница Ω(1).

Можно ли определить границы и для других случаев (лучший, средний)?

Да. Возможно, что все случаи имеют свои верхнюю и нижнюю границы.

Answer 2

Почти никогда не обсуждается лучший случай. Это просто не так интересно. Алгоритм всегда можно изменить, чтобы иметь наименьший теоретически возможный лучший случай, который равен O(max(размер входа, размер выхода)), просто путем распознавания одного конкретного входа и получения выходных данных, предварительно рассчитанных для этого входа. В бенчмаркинговом бизнесе это называется обманом.

Термин "связанный здесь" имеет то же значение, что и в остальной части математики, а именно произвольное значение, которое не больше (не меньше), чем любой элемент данного набора.

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

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

С другой стороны, мы можем обсудить конкретный алгоритм сортировки и доказать, что он никогда не превышает определенного количества операций, что было бы верхней границей его сложности. Например, алгоритм быстрой сортировки имеет верхнюю границу O (n ²). Он также имеет верхнюю границу O (n ³). Он не имеет верхней границы O(n log n), потому что есть входы, которые превышают это число операций. Граница O (n ²) является жесткой, потому что она достигается для некоторых входов.

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

Мы также можем обсудить сложность конкретной проблемы и наложить на нее как верхнюю, так и нижнюю границы. Насколько эффективен наиболее эффективный алгоритм (в худшем или среднем случае), который его решает? (Мы не обсуждаем лучший случай, потому что ответ не интересен, см. Выше). Для задачи сортировки, основанной на сравнении, мы знаем, что как жесткая верхняя граница, так и жесткая нижняя граница являются O(n log n), поскольку на самом деле существуют алгоритмы сортировки O(n log n), и можно показать, что лучшего алгоритма нет существует. Это не очень интересный случай, потому что мы можем найти наиболее эффективный алгоритм из возможных. Например, проблема с ранцем, ситуация более интересная. Мы знаем только, что верхняя граница O (n ²) существует, потому что алгоритм с такой сложностью существует тривиально (грубая сила). Мы подозреваем, но не можем доказать, что эта граница жесткая. Мы также не можем предоставить какую-либо хорошую нижнюю границу (мы подозреваем, что нет алгоритмов, которые решают ее с полиномиальной сложностью, но не могут доказать это).