Алгоритмы, верхние / нижние границы и лучший / худший случай

Question

Для алгоритмов, как границы связаны с лучшими / худшими случаями? Является ли худший случай синонимом верхней границы, а лучший - синонимом нижней границы? Или вы можете по крайней мере вывести одно из другого? Или они вообще не связаны?

Answer 1

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

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

Что касается вашего последнего вопроса, да, мы можем использовать метрику среднего случая, чтобы сжимать / решать либо для худшего, либо для лучшего сценария. Пусть O, Θ, Ω представляют наихудший случай, средний случай и лучший случай, соответственно, и f (n) и g (n) две произвольные функции.

1) Если f(n) = O(g(n)) и f (n) = Θ (g (n)) ==> f(n) = Ω(g(n))
2) Если f(n) = Ω(g(n)) и f(n) = Θ(g(n)) ==> f(n) = O(g(n))

Answer 2

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

В лучшем случае мы рассчитываем нижнюю границу времени выполнения алгоритма. Мы должны знать случай, который приводит к выполнению минимального количества операций. В задаче линейного поиска наилучший случай возникает, когда x присутствует в первом месте. Анализ Best Case является поддельным. Гарантия нижней границы алгоритма не дает никакой информации, так как в худшем случае алгоритм может занять годы.