Исследуя большую нотацию O, я понимаю концепцию O (log n) как двоичный поиск и O (n log n) как быструю сортировку.Как O (n log n) отличается от O (log n)?
Можно ли положить в неспециалист условия, что основное различие в выполнения между этими двумя? и почему это так?
они кажутся интуитивно аналогичным образом связаны
В основном: фактор N.
Двоичный поиск только затрагивает небольшое число элементов. Если есть миллиард элементов, бинарный поиск касается только ~ 30 из них.
Быстрая сортировка затрагивает каждый элемент, небольшое количество раз. Если есть миллиард элементов, то быстрый сорт касается всего из них, примерно 30 раз: около 30 миллиардов штрихов.
является прецедентом для двоичного поиска, который должен быть заказан, где быстрая сортировка - лучший случай случайного ввода? –
Бинарный поиск находит значение в упорядоченном списке. Быстрый сортир - это способ сортировки списка. Они вообще не связаны друг с другом. –
Хорошо, я вижу, что ты говоришь ... я думаю, мне нужно было знать, что бинарный поиск должен был заказать вход –
на простых условиях и визуализации, они являются своего рода то же самое в алгоритмы сортировки, но быстрой сортировки, как O (п § п) имеет недостаток в некоторых ситуациях, быстрая сортировка большинства ситуаций является лог н, но в особых случаях - n², поэтому n до log n. Так что быстрый сортировка для небольшого количества сортировки очень хороша, но для миллионов/миллиардов ее нет, лучше использовать Merge Sort для такого рода сортировки.
Или, поскольку quicksort намного быстрее, чем сортировка слияния, вместо этого используйте [Introsort] (https://en.wikipedia.org/wiki/Introsort), который обычно выполняется так же быстро, как и quicksort, но не переходит в n^2 , –
«Быстрая сортировка большинства ситуаций - log n, но в особых случаях это n², поэтому n до log n» имеет мало смысла. Вы действительно хотели это сказать? Quicksort - это * never * 'log n', и нет общей теоремы, в которой говорится, что если алгоритм является« O (n^2) »наихудшим случаем, тогда средняя сложность -« O (n log n) »- это очень особенное свойство quicksort. –
Посмотрите, как Log(n) плоская, в то время как nLog(n) пересекла 600 для значения п = 100. То, как они отличаются.
'Log (n)' не _quite_ flat. –
@MooingDuck: для n = 100 и базой 10, n = 10. Сравнивая его с 600, он почти * плоский. – displayName
Моя точка зрения заключалась в том, что ответ говорит, что он плоский. Нужен квалификатор. –
Они совсем разные: http://bigocheatsheet.com/ – Jack
Поскольку 'n log n' - это другая функция из' log n', которая растет намного быстрее, почему они должны быть одинаковыми? Это 'n' имеет большое значение: если' log' является базой 2 и 'n = 1000',' n log n' является '9965.8', но' log n' является просто '9.97'. –
Почему downvotes, если есть комментарии? –