złożoność algorytmów

Question

Mimo, że pojawiło się tutaj kilka takich pytań... ja nadal nie rozumiem obliczania złożoności algorytmów... Jak odróżnić O od Omegi czy od Tethy...
Jak się zabrać do obliczania tej złożoności w najprostszych programach?

Będę bardzo wdzięczna za wytłumaczenie.

Z góry dziękuję! :)

Answer 1

Złożoność się zapisuje za pomocą dużego O( i tutaj złożoność) np O(n*n). Jak to się oblicza, hmm. Patrzysz na dane wejściowe i liczba tych danych to n. Jeśli robisz pętlę by je wczytać to jest to złożoność O(n). Jeśli w tej pętli co wczytujesz dane zagnieżdżasz inna pętle to będzie już złożoność O(n*m) gdzie m to liczba obiegow tej zagniezdzonej pętli. Stałą programu pomijasz np O( 10*n) pomijasz te 10

Comments

i to jest ta pesymistyczna?
A co z tymi gdzie występuje jakiś logarytm?

---

Tak zawsze podajemy pesymistyczna wartość. Lugarytm to np jak robisz wyszukiwanie binarne to masz złożoność log n

---

a jeśli mam dwie pętle, ale nie zagnieżdżone w sobie, to sumujemy ? i będziemy mieli 2n?

---

Czytaj ze zrozumieniem. Będziesz miała czas n stała programu pomijasz czyli twoja 2.

---

ahaaa :) okej, to teraz rozumiem, przynajmniej tą część :) dziekuję

a jeszcze jest cos takiego jak twierdzenie o rekursji uniwersalnej. To w praktyce, gdzie je stosujemy?

---

Pierwszy raz słyszę ten termin. Potem poczytam i odpiszę co i jak

---

ok, w takim razie dziękuję bardzo :)

---

http://smurf.mimuw.edu.pl/node/829 Tu jest dość sensownie napisane o tym twierdzeniu

---

a mam takie zadanie:

Wyznacz złożoność czasową T(n) spełniającą zależność T(n)=4T(n/2)+f(n) algorytmów rekurencyjnych A1, A2, A3, A4 jeśli dla kolejnych A1, A2, A3, A4 zachodzi:
a) f(n)=n^3
b) f(n)=n^2
c) f(n)=n
d) f(n)=nlogn
Gdybym mogła prosić o wskazówkę albo jeden podpunkt, żebym wiedziała jak to dalej liczyć... byłabym wdzięczna :)

---

Zakładając, że rozumie treść zadania ( nie wiem o co chodzi dokładnie  A1, A2 itd.) To pomyśl ile razy wykonasz funkcję T(n) ( pomijamy narazie f(n) ). Załóżmy że nasze n = 10 . To się  funkcja wykona tak: T(10 ) = 4 * T ( 5 ) , potem T(5) = 4*T(2), następnie T(2) = 4*T(1) i T(1) = 4*T(0). Z tego wynika, że  stopień zagłębienia funkcji T(N) wynosi log2(n)+1  ( w tym przypadku ( 4 poziomy zagłebiania ) .  Okej mamy jedną część, teraz uwzględnimy tą czwórkę, za każdym razem wykonuje się 4 razy T(n) czyli ogólna liczbą wywołań funkcji T( n )  to około 4^ log2(N)+1. Teraz zobacz, że każdemu wywołaniu towarzyszy funkcja f( n ) o złożoności n^3.

Czyli złożoność wynosi 4^(log2(N)+1) *  złozoność funkcji czyli dla przykładu A to wynik wynosi 4^(log2(n)+1)*n^3. Mam nadzieję, że wszystko jest OK i przepraszam za błędy

Answer 2

Mówiąc najprościej, złożoność obliczeniowa (zapewne chodzi ci o tzw. czasową złożoność obliczeniową) to ilość różnych operacji jakie będą się wykonywać w algorytmie (przypisywanie wartości do zmiennych, warunki itp.). Jeżeli np. skanujesz jakiś wektor od początku do końca (pętla for), a dla każdego (bądź tylko niektórych) elementu będziesz przypisywać jakąś wartość to algorytm będzie miał czasową złożoność obliczeniową zbliżoną do O(n), gdzie [n] to wielkość wektora.. jeżeli, w algorytmie będziesz miała do czynienia z tablicą 2-wymiarową to złożoność będzie zbliżona do O(n^2). Jeżeli na przykład czasowa złożoność obliczeniowa wynosi O(n^3) gdy da się taki sam algorytm napisać o złożoności obliczeniowej O(n*logn) to możemy bez problemy wywnioskować, który jest szybszy.
PS Czasowa złożoność obliczeniowa często jest mylona z czasem wykonywania się programu/algorytmu. Jest to błędne rozumowanie.