Odpowiedzi

Najlepsza Odpowiedź!
  • KuRo
  • Rozwiązujący
2010-01-07T19:38:49+01:00
Najłatwiej wytłumaczyć na przykładzie.

> Przykład 1

Wyszukiwanie wartości maksymalnej w ciągu nieposortowanym
Załóżmy, że masz n liczb. Potrzebujesz przejrzeć każdą z nich po to, by określić która z nich jest największa. Potrzebujesz zatem n operacji ("spojrzeń) - liczba potrzebnych operacji jest proporcjonalna do rozmiaru ciągu - więc złożoność liniowa, O(n).

> Przykład 2

Wyszukiwanie danej liczby w ciągu posortowanym
Pomyśl jakąś liczbę od 1 do 1000. Teraz ja zgadnę jaką pomyślałeś, zadając Ci maksymalnie 10 pytań:

Czy ta liczba jest mniejsza od 500?
Jeśli tak, to czy jest mniejsza od 250?
Jesli nie, to czy jest mniejsza od 375?
Jeśli nie, to czy jest mniejsza od 438?
Jeśli nie, to czy jest mniejsza od 469?
Jeśli tak, to czy jest mniejsza od 443?
Jeśli tak, to czy jest mniejsza od 440?
Jeśli tak, to tą liczbą jest 439.

Idea jest taka, że dzięki temu, że ciąg jest posortowany, cały czas pomniejszasz sobie zakres, w którym masz szukać o połowę - dzięki temu potrzebujesz tylko ok. log21000 operacji - a więc masz złożoność O(log2n) - logarytmiczną.

> Przykład 3

Sortowanie przez wybieranie
Masz nieposortowany ciąg o n elementach i posortowany o 0 elementach. Szukasz najmniejszego elementu w ciągu nieposortowanym i wstawiasz go na koniec posortowanego ciągu, tyle razy, aż posortowany ciąg będzie miał n elementów, a nieposortowany 0. Taki stan uzyskasz wtedy, gdy wszystkie n elementów z nieposortowanego przerzucisz w posortowany. Musisz zatem n razy wyszukać najmniejszy element w ciągu - a wyszukiwanie najmniejszego elementu, jak wiemy z 1. przykładu, ma złożoność O(n) (liniową). Zatem wykonanie n razy operacji o złozoności n wymaga n*n operacji, czyli ma złożoność O(n*n) = O(n2) - kwadratową.