Musze zrobić prezentacje na przedmiot podstawy algorytmizacji.
Jestem na studiach zaocznych, 1 rok miałem dopiero 2 zjazdy a gosc nam z takimi tematami...
Mój temat brzmi: Wyznaczanie złożoności obliczeniowej (klasy funkcji) na dowolnych 3 przykładach
Informacje na temat złożoności obliczeniowej juz mam.
Znalazłem też kilka przykładów niestety wogóle ich nie rozumiem...
Znalazłem kilka przykładów, ale nie mam pojecia jak sie to wogóle odczytuje, może ktoś mi napisze?
(nawet nie wiem czy to przykład)
Ktoś na forum kiedyś napisał...
Tylko nie wiem czy takie przykłady się nadają do tej prezentacji
Cytat
Na tzw. ruskiego czuja, ew. na tzw. oko.
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ą.
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ą.