Алгоритмическая сложность итерирования по хэшсету в C#

[DNNX]

Совершенно верно. Любое удаление элементов из хэшсета в дотнете не ведёт к сужению таблицы. Для этой цели в классе введён специальный метод TrimExcess().

[DNNX]

И, кстати, MSDN опять врёт: там сказано «This method is an O(n) operation, where n is Count.»

В случае дырявого хэшсета цикл, который внутри этого метода, будет бежать по всем дыркам подряд, количество которых, вообще говоря, не зависит от n и может быть на порядки больше его.

[DNNX]

В википедии не написано о том, как реализован _дотнетовский_ хэшсет. Читайте, пожалуйста, внимательно, о чём я пишу.

[DNNX]

И, да: если я не прав, то какая, по-вашему, временная сложность пробежки по всем элементам дотнетовской реализации хэшсета?

[easyman]

pastebin.org/413645
отсюда удобнее копипастить

[KAndy]

O(n^2) для QuickSort в худшем случаи, это особенность алгоритма а не реализации в С#

[DNNX]

Бесспорно, это так. Я лишь хотел заострить внимание на примитивности реализации квиксорта в дотнете. Когда реализацию быстрой сортировки можно «сломать» таким простым набором данных, это не говорит в пользу этой реализации. Сравните, например, с алгоритмом квиксорта в джаве. Там алгоритм выбора медианы не такой школьный, как в дотнете, и найти класс данных, на которых время сортировки будет квадратичным, горааздо сложнее.

[Zorkus]

В Java есть специальные библиотеки для высокопроизводительных коллекций — trove4j.sourceforge.net/. Уверен для дотнета есть такое же.

[KAndy]

> Я лишь хотел заострить внимание на примитивности реализации квиксорта в дотнете.

А смысл что-то усложнять. Если нужно гарантировано O(n*Lg(n)) нужно выбрать соответствующий алгоритм.

А так получается пост о вашем отношении…

Так же «This method is an O(n) operation, where n is Count.» в среднем случаи работает, хотя Вы и придумали худший :)…

[shai_hulud]

Я прямо с ходу вижу уши Java в этом топике. Реализация Quicksort'а давно стала хрестоматийной в разжигании холиворов.