AKB Forums

Go Back   AKB Forums > Technical sections > Algorithms
Home Register Blogs FAQ Members List Calendar Downloads Arcade Mark Forums Read

Algorithms The source of algorithms for your project

Troubles when posting message? Click here! :: Проблемы с отправлением сообщения? Нажмите сюда!

Reply
 
LinkBack Thread Tools Display Modes
Old May 7, 2004, 09:18   #1
Грустно...
 
Agregat's Avatar
 
Join Date: Aug 2002
Location: Там, где всегда идут дожди
Posts: 21,637
Rep Power: 11
Reputation: 211
Send a message via ICQ to Agregat Send a message via MSN to Agregat
Для любителей оптимальных алгоритмов

В голову пришел чудо - алгоритм сортировки, выглядит следующим образом. Несмотря на страшный вид пользоваться им можно элементарно.
PHP Code:
template<class BidirectionalIterator, class StrictWeakOrdering
void best_sort (BidirectionalIterator firstBidirectionalIterator lastStrictWeakOrdering comp) {
 while (
next_permutation(firstlastcomp)); 

Для пытливых умов, предлагаю оценить временные затраты в терминах большого О.
__________________
http://аvitya.livejournal.com
Хотели, как лучше, а получилось даже хуже...
Лозунг шахматиста: На каждый шах - ответим матом!
Agregat is offline   Reply With Quote Quote selected
Old May 7, 2004, 18:41   #2
Painfully Outlandish
 
gaglik's Avatar
 
Join Date: May 2003
Location: Albainn
Posts: 113
Rep Power: 6
Reputation: 10
Quote:
Originally Posted by Agregat
В голову пришел чудо - алгоритм сортировки, выглядит следующим образом. Несмотря на страшный вид пользоваться им можно элементарно.
PHP Code:
template<class BidirectionalIterator, class StrictWeakOrdering
void best_sort (BidirectionalIterator firstBidirectionalIterator lastStrictWeakOrdering comp) {
 while (
next_permutation(firstlastcomp)); 

Для пытливых умов, предлагаю оценить временные затраты в терминах большого О.
Vo pervyx algoritm suschestvoval i do etogo.
Vo vtoryx chudom ego nazvat' nikak nel'zya t.k. optimal'nye algoritmy (based on comparisons) sortiruyut O(NlogN), i dokazano chto bystree ne vozmojno, a etot algoritm sortiruet O(N!), esli pomelochit'sya O(N*N!), chto namnogo medlennee chem daje exponencial'noe vremya.

Take care.
gaglik is offline   Reply With Quote Quote selected
Old May 7, 2004, 18:46   #3
Painfully Outlandish
 
gaglik's Avatar
 
Join Date: May 2003
Location: Albainn
Posts: 113
Rep Power: 6
Reputation: 10
And the algorithm is "surprisingly" called snail sort.
gaglik is offline   Reply With Quote Quote selected
Old May 7, 2004, 22:50   #4
Грустно...
 
Agregat's Avatar
 
Join Date: Aug 2002
Location: Там, где всегда идут дожди
Posts: 21,637
Rep Power: 11
Reputation: 211
Send a message via ICQ to Agregat Send a message via MSN to Agregat
1. На первый пост: во - первых я не сказал, что я его выдумал, я сказал, что он мне пришел в голову. Во - вторых, я не знаю, что ты подразумеваете под based on comparisons, но Bucketsort основанный на сравнение (comparison) на равенство однозначно 2*N без больших О. В - третьих посмотрите в толковом словаре слово сарказм.

2. Вы не первый, кто отметил, что я не первый кто это (алгоритм) заметил. www.sgi.com и далее пока не дойдете до STL docs это содержат. Специально для вас еще один крутой алгоритм:
PHP Code:
template <typename RanIt
void bogosort (RanIt firstRanIt last

while (
std::adjacent_find(firstlaststd::greater<typename std::iterator_traits<RanIt>::value_type>()) != last
std::random_shuffle(firstlast); 

Идея не моя, реализация моя, хотя если копнуть в гугле найдете подобное, я не сомневаюсь, но это уже домашнее задание. Докажите его линейность (!) и приведите условия для доказательства линейности в худшем случае, при этих условиях, в худшем случае без подобных условий, как понятно тот же O(N!), но так как алгоритм случайный - можеы быть как хуже так и лучше
__________________
http://аvitya.livejournal.com
Хотели, как лучше, а получилось даже хуже...
Лозунг шахматиста: На каждый шах - ответим матом!
Agregat is offline   Reply With Quote Quote selected
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Расширение кругозора - 2 greka Software Security 3 Jan 9, 2004 09:30
для любителей футбольной статистики tig Sport 1 Aug 14, 2003 09:42
Для Любителей Ченого :) Timewind Fun 0 Jun 21, 2003 07:48
Неплохие линки для любителей UT -=iR0Nr@T=- Games 1 Aug 14, 2002 20:28


All times are GMT. The time now is 14:20.


Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
This board was founded on September 29, 2001
Powered by Viper Internet

Affordable Web Hosting | ParevNet

Buy text link