Войти
ФлеймФорумПрограммирование

Существует ли такая сортировка? (7 стр)

Страницы: 13 4 5 6 7 8 Следующая »
#90
20:14, 5 янв 2015

laMer007
> Существует асинхронная сортировка за O(n).
На 3-й странице уже советовали. Но среди алгоритмов O(n) мне больше всего Quantum Bogosort нравится

#91
20:28, 5 янв 2015

kipar
> На 3-й странице уже советовали.
Ага:
http://www.gamedev.ru/flame/forum/?id=196521&page=3#m43
Небось за это и забанили автора. Мегатехнология. Небось под покровительством гос спецслужб.

#92
22:03, 5 янв 2015

Ну и заодно на C#:
http://rextester.com/PHIRI57951
Интересно, а как с async \ await убрать потоки совсем? Внизу показывает 8. Слышал как-то можно кооперативную многозадачность через них организовать при использовании ExecutionContext и SynchronisationContext.
Ну понятно что по хорошему должны быть таймеры, но это наверное не наш путь. Хотя может наш.
И кстати с async лямбдой у меня что-то не получилось.

+ Показать
#93
8:40, 6 янв 2015

статью дописал, видимо, придется еще и сам код дописать

#94
9:11, 6 янв 2015

если нужна линейно-логарифмическая сложность, O(1) памяти и последовательный доступ, то делают так:
1) делят массив на куски по k элементов каждый и сортируют любым O(1) по памяти, O(n log n) по времени и random access алгоритмом, заталкивая кусок во временный массив
2) сливают все куски аналогом меджсорта.

накладные расходы по памяти - O(k), по всем остальным критериям удовлетворяет. такие алгоритмы используются для индексации существенных объёмов данных. ну там сотня террабайт инфы какой-нибудь, например, которая в оперативку точно не влезет.

PS тред не читал

#95
15:05, 6 янв 2015

FordPerfect
Хьюстон, у нас небольшая проблема.
Я ее вроде залечил, мне надо подтверждение, не сделал ли я ошибки.

Короче, суть: в каждой вершине дерева рекурсии мы делаем O((logn)^2) операций на работу со стеком.
Возникает вопрос: а сколько у нас вообще будет вершин в дереве?
Сразу можно оценить как O(n), но тогда у нас проблемы - median of medians будет работать аж за O(n(logn)^2)
Но, по идее, их несколько меньше.
Чтобы точно посчитать, надо решить рекурренту:
Q(n) = Q(n/5) + Q(7n/10) + 1, Q(n) = 1 для n<10
надо, чтобы она росла как O(n/(logn)^2)
Я сам ее осилить не смог. Нагуглил это: https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method
Вроде же под все ограничения моя рекуррента подходит?
Если подставить циферки, то получаем, что Q(n) растет как \(\Theta\)(n^p), где 0.8 < p < 0.9
И, вроде как \(\Theta\)(n^p) = O(n/(logn)^2), т.е. все хорошо ^^
Итоговая сложность получится O(n + n^p(logn)^2) = O(n).

upd. а вообще я уже весь код написал, завтра уже выкачу статью, наверно

#96
18:50, 6 янв 2015

R.I.P.
> Ф - это такая тета большая
такая большая тета - это либо \(\theta\), либо \(\Theta\). embrace \(\LaTeX\)!

#97
19:16, 6 янв 2015

Suslik
геймдев поддерживает латех?
ну ка...
$\LaTeX$
upd. увы, не поддерживает, а картинки мне лень было вставлять. все же поняли? зачем усложнять

#98
19:18, 6 янв 2015

\(\LaTeX\)

[ cht ] \ LaTeX [ / cht ]

#99
19:27, 6 янв 2015

\(R_k = \left\{ \sum_{i=1}^n a_i w^i_k : \sum_{i=1}^n a_i w^i_k \le W_k, a \in \{0,1\}^m \right\}\)
kipar
работает! круто!
правда шрифт не латеховский, а какой-то вордовский, но, в принципе, сойдет

#100
19:29, 6 янв 2015

kipar
Спасибо. А где таким секретным знанием разживаться? При беглом просмотре http://www.gamedev.ru/site/forum/?id=124166 не увидел.

#101
19:30, 6 янв 2015

FordPerfect
Сам до этого момента не знал. Посмотрел свойства картинки сусликовской надписи.

#102
19:30, 6 янв 2015

R.I.P.
Я лично для формул до этого юзал http://www.codecogs.com/latex/eqneditor.php .

#103
19:36, 6 янв 2015

FordPerfect
Крутая рендерилка) Но у меня вроде формулы не настолько заковыристые, чтобы без латеха никак было.
Мне тут важно сейчас - в посте #95 очевидных ляпов нет?

#104
20:11, 6 янв 2015

R.I.P.
Выглядит - вроде правда.
Попробую-ка и я в LaTeX:
Изображение
http://www.wolframalpha.com/input/?i=solve+%281%2F5%29%5Ep%2B%287… 5Ep%3D1+for+p

Нет, пока встроенный LaTeX остаётся в не заюзанным.

Страницы: 13 4 5 6 7 8 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.