p
Radix sort с его O(n) к вашим услугам, хотя, это конечно, не алгоритм сортировки общего плана.
только для чисел, и с хаками)
Size: a a a
2020 May 18
IJ
Алсо, весь этот разговор кажется мне бессмысленным
IJ
Чтобы рассуждать о сложности, нужно фиксировать модель вычислений (со стоимостями операций). У обычных императивных языков она аппроксимируется ram машиной. У хаскеля модель вычислений совершенно другая. Как их сравнивать-то
IJ
И да, ленивость языка не гарантирует, что минимум путем частичной сортировки сработает за O(n)
M
Radix sort с его O(n) к вашим услугам, хотя, это конечно, не алгоритм сортировки общего плана.
А еще у него гиганское время амортизации. Он начинает быть быстрее той же быстрой сортировки только на длинах больше сотни тысяч, а то и миллионов элементов
А
Stalin sort всегда за O(n) работает. И константа хорошая.
СЛ
Stalin sort всегда за O(n) работает. И константа хорошая.
А VarlamovSort работает за O(1) тогда...
СЛ
Капитализм, счастье, сортировка за константу.
DP
за O($N)
p
Stalin sort всегда за O(n) работает. И константа хорошая.
stalin sort это
for(i:=0; i < n; i=i+1) begin?
arr[i] := 0;
end
А
stalin sort это
for(i:=0; i < n; i=i+1) begin?
arr[i] := 0;
end
нет
А
It's simple, all you need to do is iterate through the array, checking if its elements are in order. Any element that isn't in order you pull out, in other words, you send it to Gulag.
А
На самом деле их в гулаг не отправляют, а расстреливают на месте.
M
Stalin sort всегда за O(n) работает. И константа хорошая.
За O(nkvd)
А
хех
p
если будут затирать что-то про формальную верификацию, буду кидать этот репозиторий)
M
если будут затирать что-то про формальную верификацию, буду кидать этот репозиторий)
Три строчки на Ocaml и ~9000 строк доказательства на Coq =)
E
если будут затирать что-то про формальную верификацию, буду кидать этот репозиторий)
в смысле что формальная верификация раздувает код на два-три порядка?