Ĺadny brzuch
Hiho
Mam pytanie: W jaki sposób określa się złożoność obliczeniowa danego algorytmu ( czy jest liniowa, kwadratowa, logarytmiczna itp) oraz jak ją liczyć dla konkretnego algorytmu? W sieci nie mogę znaleźć nic konkretnego co byłoby jasno i prosto wytłumaczone. Bardzo proszę o pomoc.
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ą.
na studiach technicznych (zwlaszcza informatyce, zorientowanej na programowanie) jest algorytmika... popytaj jakichs studentow
na studiach technicznych (zwlaszcza informatyce, zorientowanej na programowanie) jest algorytmika... popytaj jakichs studentow
pytałem, ale nikt mi nie potrafił odpowiedzieć xD
Wielkie dzięki @bryn, trochę mi rozjaśniłeś temat. A wiesz może na czym polega liczenie złożoności dla przypadków optymistycznych, średnich i pesymistycznych? ( w jaki sposób się to robi)
Np problem wyszukiwania określonej liczby w danym ciągu liczb o długości N.
Najkorzystniejszy przypadek, to ten w którym juz przy pierszej próbie (pierwszym przebiegu pętli) odnajdziemy szukaną, więc Omin(1).
Pesymistyczny przypadek, to ten w którym szukaną odnajdujemy w ostatniej próbie, więc Omax(N)
Przypadek średni to średnia arytmetyczna numerów ostatniej pętl, więc Oś(avg(nr1,nr2,...nr3))
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Mam pytanie: W jaki sposób określa się złożoność obliczeniowa danego algorytmu ( czy jest liniowa, kwadratowa, logarytmiczna itp) oraz jak ją liczyć dla konkretnego algorytmu? W sieci nie mogę znaleźć nic konkretnego co byłoby jasno i prosto wytłumaczone. Bardzo proszę o pomoc.
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ą.
na studiach technicznych (zwlaszcza informatyce, zorientowanej na programowanie) jest algorytmika... popytaj jakichs studentow
na studiach technicznych (zwlaszcza informatyce, zorientowanej na programowanie) jest algorytmika... popytaj jakichs studentow
pytałem, ale nikt mi nie potrafił odpowiedzieć xD
Wielkie dzięki @bryn, trochę mi rozjaśniłeś temat. A wiesz może na czym polega liczenie złożoności dla przypadków optymistycznych, średnich i pesymistycznych? ( w jaki sposób się to robi)
Np problem wyszukiwania określonej liczby w danym ciągu liczb o długości N.
Najkorzystniejszy przypadek, to ten w którym juz przy pierszej próbie (pierwszym przebiegu pętli) odnajdziemy szukaną, więc Omin(1).
Pesymistyczny przypadek, to ten w którym szukaną odnajdujemy w ostatniej próbie, więc Omax(N)
Przypadek średni to średnia arytmetyczna numerów ostatniej pętl, więc Oś(avg(nr1,nr2,...nr3))