O'Reilly logo

Algorytmy. Almanach by Stanley Selkow, Gary Pollice, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required