-
Data: 2012-10-14 02:06:31
Temat: Re: sortowanie
Od: Michoo <m...@v...pl> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]On 14.10.2012 00:51, PK wrote:
> Sortowanie optymalne: max 62 porównania.
To rozwiązanie jest optymalne tylko jeżeli chodzi o liczbę porównań[*].
A nie np. czas, czy pamięć na rzeczywistym systemie(czy nawet na
abstrakcyjnej maszynie).
Możemy rozważyć mergesort na 10 procesorach - wykona trochę więcej
porównań niż Twoje "optimum", ale za to zakończy pracę prawie 2 razy
szybciej ;)
[*] Na typach bez znaku możemy sortować po kolejnych bitach. Nie
wykonujemy w takim przypadku porównań między liczbami a szukamy
pierwszej liczby z zapalonym n-tym bitem po lewej i niezapalonym po
prawej, zamieniamy, powtarzamy aż do spotkania indeksów. Powtarzamy
rekurencyjnie dla obu kawałków i n-1 bitu. Mamy 0 porównań - to dopiero
optimum ;)
--
Pozdrawiam
Michoo
Następne wpisy z tego wątku
- 14.10.12 02:19 Edek Pienkowski
- 14.10.12 02:18 M.M.
- 14.10.12 02:21 Michoo
- 14.10.12 02:29 Edek Pienkowski
- 14.10.12 02:29 bartekltg
- 14.10.12 02:43 Edek Pienkowski
- 14.10.12 02:43 bartekltg
- 14.10.12 03:05 bartekltg
- 14.10.12 03:13 Edek Pienkowski
- 14.10.12 03:39 M.M.
- 14.10.12 03:46 M.M.
- 14.10.12 04:00 bartekltg
- 14.10.12 04:07 Edek Pienkowski
- 14.10.12 04:24 M.M.
- 14.10.12 04:32 M.M.
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-02-25 Tak wiem.... To oczywiste ale jak oni dzisiaj dziadują na materiale
- 2025-02-25 rozliczenia policji
- 2025-02-25 Echhhhhh. Marzy mi się SWAP Audi A2 z 1.8 T ;-)
- 2025-02-25 Warszawa => Analityk Biznesowo-Systemowy <=
- 2025-02-25 Warszawa => SQL Developer <=
- 2025-02-25 Zbigniew Ziobro śmie sugerować "niedostatki niezawisłości" sędzi (wątpliwości co do bezstronności)
- 2025-02-25 Kraków => DevOps Engineer (Junior/Regular) <=
- 2025-02-25 Kraków => Front-end Developer <=
- 2025-02-25 Szpital
- 2025-02-24 Gniazdo + wtyk
- 2025-02-24 Dyrektor Toyoty miał rację. Elektryki to ślepa uliczka
- 2025-02-24 Białystok => System Architect (Java background) <=
- 2025-02-24 Białystok => System Architect (background deweloperski w Java) <=
- 2025-02-24 Białystok => Solution Architect (Java background) <=
- 2025-02-24 Warszawa => Data Engineer (Tech Leader) <=