Сложность бинарного поиска

Question

Я смотрю онлайн-лекцию Berkley Uni и застрял на следующем.

Проблема : Предположим, у вас есть коллекция компакт-дисков, которые уже отсортированы. Вы хотите найти список компакт-дисков, название которых начинается с «Best Of».

Решение : Мы будем использовать бинарный поиск, чтобы найти первый случай «Best Of», а затем будем печатать, пока плитка не перестанет «Best Of»

Дополнительный вопрос : найдите сложность этого алгоритма.

Верхняя граница : Верхняя граница бинарного поиска равна O (log n), поэтому, как только мы ее найдем, мы напечатаем пусть скажем k title. так что это O (logn + k)

Нижняя граница : нижняя граница бинарного поиска - Омега (1), если нам повезло, а название записи - среднее. В данном случае это Омега (к)

Вот как я это проанализировал.

Но в лекции лектор использовал лучший случай и худший случай. У меня есть два вопроса по этому поводу:

1. Почему нужно использовать наилучший и наихудший случай, разве big-O и Omega не считаются лучшим и худшим случаями, которые может выполнить алгоритм?

2. Его анализ был Наихудший случай: тета (logn + k)
   Лучший случай: Theta (k)

   Если я использую концепцию наихудшего случая как ссылку на данные и не имею ничего общего с алгоритмом, то да, его анализ прав. Это потому, что, предполагая наихудший случай (название CD в конце или не найдено), тогда Big O и Omega - это log n, там это тета (log n + k).

   Если вы не используете "лучший случай" и "худший случай", то как вы анализируете алгоритм? Мой анализ прав?

Answer 1

Почему нужно использовать наилучший и наихудший случаи, не считаются ли big-O и Omega наилучшими и худшими случаями, которые может выполнить алгоритм?

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

• Ω описывает нижнюю границу : f ( n ) ∈ Ω (g ( n )) означает асимптотическое поведение f ( n ) составляет не менее г ( n ) · k для некоторых положительных k , поэтому f ( n ) составляет всегда, по крайней мере, столько же, сколько г ( n ) · k .
• Ο описывает верхнюю границу : f ( n ) ∈ Ο (g ( n )) означает асимптотическое поведение f ( n ) составляет не более г ( n ) · k для некоторого положительного k , поэтому f ( n ) составляет , но не более г ( n ) · k .

Эти два значения могут применяться как в лучшем, так и в худшем случае для бинарного поиска:

• лучший случай: первый элемент, на который вы смотрите, это тот, который вы ищете
  • Ω (1): вам нужно как минимум один поиск
  • Ο (1): вам нужно максимум один поиск
• худший случай: элемент отсутствует
  • Ω (log n ): вам нужно не менее log n шагов, пока вы не скажете, что искомого элемента нет
  • Ο (log n ): вам нужно максимум log n шагов, пока вы не скажете, что искомого элемента нет

Видите ли, значения Ω и Ο идентичны. В этом случае вы можете сказать, что с жесткой границей для лучшего случая - Θ (1), а для худшего - Θ (log n ).

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

Если вы не делаете "лучший случай" и "худший случай", то как вы анализируете алгоритм? Правильный ли мой анализ?

Да, ваш анализ кажется правильным.

Answer 2

По первому вопросу есть разница между временем выполнения алгоритма в лучшем случае, временем выполнения алгоритма в худшем случае, big-O и big- & Omega; нотации. Время выполнения алгоритма в наилучшем и худшем случаях - это фактические математические функции с точными значениями, которые сообщают вам о максимальном и минимальном объеме работы, выполняемой алгоритмом. Чтобы описать темпы роста этих функций, мы можем использовать big-O и big- & Omega; нотации. Тем не менее, можно описать наилучшее поведение функции с помощью big- & Omega; нотация или худший случай с нотацией big-O. Например, мы можем знать, что время выполнения функции в худшем случае может быть O (n ² ), но на самом деле не знаем, какая функция O (n ² ), худшая - Случайное поведение есть. Это может произойти, если мы хотим ограничить поведение наихудшего случая, чтобы мы знали, что оно не катастрофически плохо. Возможно, что в этом случае поведение в худшем случае на самом деле является & Theta; (n), и в этом случае O (n ² ) является плохой верхней границей, но говорят, что поведение в худшем случае равно O (n ² ) в этом случае означает, что это не страшно. Точно так же мы могли бы сказать, что наилучшим поведением алгоритма является, например, Omega; (n), если мы знаем, что он должен выполнять хотя бы линейную работу, но не можем сказать, должно ли оно делать намного больше, чем это.

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

Надеюсь, это поможет!