Комментарии 12
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
pastebin.org/413645
отсюда удобнее копипастить
отсюда удобнее копипастить
O(n^2) для QuickSort в худшем случаи, это особенность алгоритма а не реализации в С#
Бесспорно, это так. Я лишь хотел заострить внимание на примитивности реализации квиксорта в дотнете. Когда реализацию быстрой сортировки можно «сломать» таким простым набором данных, это не говорит в пользу этой реализации. Сравните, например, с алгоритмом квиксорта в джаве. Там алгоритм выбора медианы не такой школьный, как в дотнете, и найти класс данных, на которых время сортировки будет квадратичным, горааздо сложнее.
В Java есть специальные библиотеки для высокопроизводительных коллекций — trove4j.sourceforge.net/. Уверен для дотнета есть такое же.
> Я лишь хотел заострить внимание на примитивности реализации квиксорта в дотнете.
А смысл что-то усложнять. Если нужно гарантировано O(n*Lg(n)) нужно выбрать соответствующий алгоритм.
А так получается пост о вашем отношении…
Так же «This method is an O(n) operation, where n is Count.» в среднем случаи работает, хотя Вы и придумали худший :)…
А смысл что-то усложнять. Если нужно гарантировано O(n*Lg(n)) нужно выбрать соответствующий алгоритм.
А так получается пост о вашем отношении…
Так же «This method is an O(n) operation, where n is Count.» в среднем случаи работает, хотя Вы и придумали худший :)…
Я прямо с ходу вижу уши Java в этом топике. Реализация Quicksort'а давно стала хрестоматийной в разжигании холиворов.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмическая сложность итерирования по хэшсету в C#