Proszę o wyjaśnienie w jaki sposób liczy się złożoność obliczeniową? :/

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