-
Data: 2015-07-15 22:55:00
Temat: Re: Kiedy qsort zaczyna źle działać?
Od: Pit <n...@s...lonestar.org> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]Dnia 15.07.2015 Borneq <b...@a...hidden.pl> napisał/a:
> QSort w najgorszym przypadku jak słyszałem, ma złożoność kwadratową.
> Kiedy występuje ten najgorszy przypadek? Kiedy dane są już posortowane?
> czy też jest to jeden specyficzny porządek, na którego natrafienie jest
> trudniejsze niż wygranie w toto lotka?
Zależy nie tyle od samego posortowania, co od wyboru elementu wg którego
"dzielisz" zbiór. Jeśli "pechowo" zawsze trafisz w element największy
(lub najmniejszy) to dostajesz podział na zbiór jednoelementowy i "resztę"
(czyli nie dość że takie "pechowe typowania" sortują tak na prawdę tylko
jeden element a reszta pozostaje jak było, to jeszcze rośnie
zapotrzebowanie na pamięć stosu, bo rekurencja idzie bardzo głęboko).
Następne wpisy z tego wątku
- 15.07.15 23:06 Borneq
- 15.07.15 23:08 Borneq
- 15.07.15 23:10 bartekltg
- 15.07.15 23:11 bartekltg
- 15.07.15 23:18 Borneq
- 15.07.15 23:37 bartekltg
- 16.07.15 01:39 Pit
- 16.07.15 08:31 Borneq
- 16.07.15 11:43 firr
- 18.07.15 21:30 Wojciech Muła
Najnowsze wątki z tej grupy
- 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??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
Najnowsze wątki
- 2025-01-06 Jeździ, skręca, hamuje
- 2025-01-06 Białystok => System Architect (Java background) <=
- 2025-01-06 Gliwice => Specjalista ds. public relations <=
- 2025-01-06 Białystok => Solution Architect (Java background) <=
- 2025-01-06 Zielona GĂłra => Konsultant WdroĹźeniowy Comarch XL/Optima (KsiÄgowoĹ
- 2025-01-06 Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- 2025-01-06 Ostrów Wielkopolski => Area Sales Manager OZE <=
- 2025-01-06 Do IO i innych elektrooszolomow, tu macie prawdziwe smrody
- 2025-01-06 Białystok => Full Stack .Net Engineer <=
- 2025-01-06 Kraków => Business Development Manager - Network and Network Security
- 2025-01-06 Katowice => Regionalny Kierownik Sprzedaży (OZE) <=
- 2025-01-06 Warszawa => Spedytor Międzynarodowy <=
- 2025-01-06 Lublin => Programista Delphi <=
- 2025-01-06 Gdańsk => Specjalista ds. Sprzedaży <=
- 2025-01-06 śnieg