magog
26.07.2012 05:21 mcabber
Если для наихудшего случая сложность равна O (1), то какая тогда сложно может быть для лучшего случая?
28 comments
recommend
bookmark
subscribeDo you really want to delete ?
- within threads
- within tags
- within users
Тоже O(1), средний случай тоже O(1).
Смысл символики Ландау (в терминах пределов отношений) почитай что ли.
Меня беспокоят такие мысли в твоей голове =)
думаешь, магог спрашивал не из желания просто попиздеть^W^W^W философских побуждений?
Я дал ответ, который считаю близким к истине :)
нахуй тогда писать, что эта сложность в худшем случае, если она тога всегда такая?
Потому что оценка алгоритмов в принципе интересна только в худшем и среднем случаях. А то, что оценка говорит о константном времени в худшем случае, сразу же влечет, что константное время нужно и в лучшем, и в среднем.
Ваш кэп.
дебилизм. почему не написать: сложность алгоритма всегда О (1)?
Потому что ежу понятно, что если в худшем O(1), то всегда O(1). Потому что если было бы O(logN), скажем, то это еще не означает, что в лучшем и среднем столько же. Это единообразие обозначений. Ты предлагаешь из-за тривиального случая вводить особые обозначения и формулировки, промто для того, чтобы разжевать простейшее следствие ?
да я понимаю ситуацию с o (log n), но худший случай o (1) ввел меня в ступор.
нихуя. у некоторых видов сортировок как раз очень интересен может быть и наилучший случай
просто при доказательстве кто-то оценил сверху и получил константу. и для красного словца оценку сверху назвал «худшим случаем»
bogosort, ага. Там такая разительная разница :)
тащем-там я имел в виду пузырёк, для случая, когда порядок нарушен лишь частично
правильно сделал, я щетаю
а, ты про оптимизированный пузырек с флажком ? Ну да, если это не учитывать, то суть оптимизации не раскрыть.
а кто-то использует неоптимизированные пузырьки?
а кто-то использует пузырьки ?
Кнут, например. В третьем томе. Так что можно сказать, что кто-то использует пузырьки для работы и зарабатывает на этом неплохие деньги
думаешь сейчас еще есть те, которые знают, что сортировать можно отличным от std::sort (замени на любую сортировку в фреймворке)?
есть, не обольщайся
щоб ты знал, ещё есть std::stable_sort.
дада :)
в питушоне тоже не quick sort используется, а собственный гибрид
внезапно знаю.
да вот он: http://en.wikipedia.org/wiki/Timsort
опять же, если читаешь данные со стрима поэлементно, то имеет смысл сортировать деревом %) например, засыпая элементы в std::set. После окончания чтения с потока вываливать этот std::set куда (в тот же vector простым std::copy).
я уже пожалел, что написал свой коммент