[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение теории
Author Message
Fedor Korobeynikov

Topics: 46
Messages: 162

My Profile
Я на Сodeforces не раз нарывался на то, что обычный QuicqSort не проходит. Там на форумах почитал про то, что существуют тесты AntiQuickSort, но для рандомизированного они почти всегда проходят. Сам убедился, что это так. В видео лекции А.Станкевича он говорит, что надо пользоваться всегда рандомизированным. Я же не могу не верить таким людям. Сегодня решая задачу Сow из Сanada 2007 у меня получилось, что рандомизированный берет только 80 баллов, на 9 тесте снято по времени, а обычный берет все. Так как мне понять, когда какой надо писать. Вы конечно можете мне сказать, что не нравится QuikSort пиши HeapSort он гарантированно за n*log(n) работает(зато больше кода), но я хочу понять когда какой QuickSort надо писать. Может время выполнения задачи тогда не корректно установлено?

______________________
Work hard and win a prize
Aleksey Gulenko

Topics: 4
Messages: 165

My Profile


Федя Коробейников:

Так как мне понять, когда какой надо писать. 

Недостаток этого алгоритма сортировки в том, что он практически всегда работает медленнее, чем другие логарифмические, и любая его реализация может на каком-то тесте дать квадратичное время. Поэтому, если хочешь гарантированный логарифм, используй сортировку кучей или слиянием.


Федя Коробейников:

(зато больше кода) 

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


Федя Коробейников:

он говорит, что надо пользоваться всегда рандомизированным 

Преимущество рандомизированного варианта в том, что для него нельзя составить тест, который гарантированно будет ломать ему показатели. На практике, значение в середине интервала ничуть не хуже и не лучше, чем любое другое, подходит в качестве контрольного. И на олимпиаде, использование числа из случайной позиции наверняка даст тот же результат, что и любой другой нестандартный (не-серединный) вариант: хоть самое левое число бери, хоть третье справа. А хочешь - полусумму крайних чисел
На собственно скорость сортировки рандом здесь ну никак не влияет.

P.S. BTW: не Quiq, а Quick, и не Heep, а Heap
______________________
// LeX
 
Forum Index ->Олимпиадное программирование ->Обсуждение теории
Time:0,047