eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingKiedy qsort zaczyna źle działać?Re: Kiedy qsort zaczyna źle działać?
  • 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).

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: