Для алгоритмов, как границы связаны с лучшими/худшими случаями? Является ли худший случай синонимом верхней границы, а лучший случай синонимом нижней границы? Или вы можете хотя бы извлечь один из другого? Или они вообще не связаны?Алгоритмы, верхние/нижние границы и наилучший/худший случай
В анализе наихудшего случая мы вычисляем верхнюю границу времени работы алгоритма. Мы должны знать случай, который вызывает максимальное количество операций. Для линейного поиска худший случай возникает, когда элемент, который нужно искать (x в приведенном выше коде), отсутствует в массиве. В большинстве случаев мы проводим анализ худшего случая для анализа алгоритмов. В худшем анализе мы гарантируем верхнюю границу времени работы алгоритма, который является хорошей информацией.
В лучшем анализе случаев мы вычисляем нижнюю границу времени работы алгоритма. Мы должны знать случай, который вызывает минимальное количество операций. В задаче линейного поиска наилучший случай возникает, когда x присутствует в первом местоположении. Анализ лучших случаев - фиктивный. Гарантия нижней границы алгоритма не дает никакой информации, как в худшем случае, для выполнения алгоритма могут потребоваться годы.
Да, это может означать худший случай, синонимом верхней границы и наилучшего случая, синонимом нижней границы.
Показатели наихудшего случая наиболее часто используются в анализе алгоритмов. В худшем случае мы гарантируем верхнюю границу времени работы алгоритма, который является хорошей информацией. Другими словами, мы должны найти выполнение, которое вызывает максимальное количество операций. Хотя в анализе наилучшего случая мы вычисляем нижнюю границу времени работы алгоритма. Мы должны знать случай, который вызывает минимальное количество операций.
Что касается вашего последнего вопроса, да, мы можем использовать среднюю метрику для сжатия/решения для наихудшего или наилучшего сценария. Пусть 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))
Я понимаю, что лучший случайный сценарий, как правило, не очень полезен, но я читал, что нижняя граница алгоритма важна b/c, это доказывает, что ни один алгоритм не может сделать лучше. Значит ли это, что нижняя граница и лучший случай - две разные вещи? –
Типичное доказательство нижнего предела говорит о том, что любой алгоритм решения проблемы должен занимать не менее времени f (n) - например. любой вид, используя только сравнения, должен сделать как минимум n lg n сравнения в худшем случае. Это не то же самое, что лучший сценарий, который может сказать, например, что сортировка пузырьков в лучшем случае делает только n сравнения. – mcdowella
@ K-Smoove лучший случай является синонимом нижней границы, или я бы сказал, что в лучшем случае мы рассмотрим нижнюю границу времени работы. – Deepak