Comments 10
Очень интересно. В виде кода, правда, не очень (с некоторым трудом могу представить практическое применение) — разве что один раз сравнить с другими и забыть (кстати, где количество операций для среднего и наихудшего случая?), а вот вживую с колодой надо будет попробовать…
+1
в худшем (когда карты в обратном порядке) кучек будет n, значит мы должны будем сравнивать каждую карту с каждой кучкой — получаем n^2 сравнений.
+1
мы должны будем сравнивать каждую карту с каждой кучкой
Нет, кучки упорядочены, мы можем использовать бинарный поиск. Так что n*log(n)
+2
N кучек будет в случае прямого порядка, нет? В обратном кучка как раз будет одна.
+2
Почему? В случае обратно отсортированного массива будет одна кучка, т.е. один стек, из которого мы все значения и вытащим обратно (сравнивая каждое с одним другим значением). O(n).
В случае отсортированного массива будет как раз n кучек, из каждой кучки мы добавим по одной карте в очередь, из которой мы вытащим все значения обратно (ни с чем не сравнивая). O(n)
Не?
В случае отсортированного массива будет как раз n кучек, из каждой кучки мы добавим по одной карте в очередь, из которой мы вытащим все значения обратно (ни с чем не сравнивая). O(n)
Не?
+1
В том то и дело, что реверс — это не худший случай, а лучший.
В этом случае создастся всего одна стопка (напомню, что стопки всегда обратно упорядочены).
В этом случае создастся всего одна стопка (напомню, что стопки всегда обратно упорядочены).
0
nlogn для массива изначально отсортированного в обратном порядке.
И n дополнительной памяти. При этом ее надо выделять очень хитро. Одним куском не выделить. Чую там накладных расходов море будет.
Зачем? Есть же mergesort и quicksort. Один гарантирует nlogn при n памяти выделенной одним куском, второй nlogn при минимальном везении и in place работает.
А для колоды и прочих таких случаев bucket sort. Его не обойти.
И n дополнительной памяти. При этом ее надо выделять очень хитро. Одним куском не выделить. Чую там накладных расходов море будет.
Зачем? Есть же mergesort и quicksort. Один гарантирует nlogn при n памяти выделенной одним куском, второй nlogn при минимальном везении и in place работает.
А для колоды и прочих таких случаев bucket sort. Его не обойти.
+1
от 30 до 39 (да, конечно, внутри масти количество карт не равно ровно десяти, но вы поняли, что имеется ввиду).от 30 до
+1
Sign up to leave a comment.
Пасьянсная сортировка