Rozdział 4. Algorytmy sortowania
Przegląd
Jak szybko potrafisz określić, czy stan Wyoming występuje w spisie stanów pokazanym na Rysunek 4-1? Możliwe, że odpowiesz na to pytanie w niecałą sekundę. Ile zabrałoby to czasu, gdyby spis miał 1000 słów? Dobrym oszacowaniem byłoby 100 sekund, ponieważ rozmiar problemu zwiększył się stukrotnie. A czy mając tę samą listę nazw stanów, potrafisz określić, ile spośród nich kończy się literą s? Zadanie to jest zaskakująco łatwe, gdyż szybko spostrzeżesz, że stany są posortowane rosnąco według ich ostatnich znaków. Gdyby słowa w spisie 1000-elementowym były posortowane podobnie, zadanie to zabrałoby zapewne tylko kilka sekund więcej, ponieważ można by zrobić użytek z uporządkowania słów na liście.
Rysunek 4-1. ...
Get Algorytmy. Almanach now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
