Algorytmy, złożoność obliczeniowa


(Ragnar) #1

~~


(Pablo_Wawa) #2

A dlaczego tak uważasz? Mnie się wydaje, że złożoność jest O(N), bo ja widzę tu tylko 3 razy pętle niezagnieżdżone (max 3*N).


(Ragnar) #3

Na samym końcu schematu blokowego jest chyba pętla zagnieżdzona

  1. for (Aw=m, Aw <=N, Aw+1)

6.1 for (Bw=m, Bw <=M, Bw+1)

Porównywany jest element z pierwszej tablicy A z elementami drugiej tablicy B. Jeżeli sprawdzany warunek nie jest spełniony to brany jest kolejny element z tablicy B a jeżeli spełniony to wypisywany jest aktualny element, i brany jest kolejny element z tablicy A itp.

Z tego co wiem to w przypadku pętli niezagnieżdżonych wystarczy policzyć iteracje ja naliczyłem ich pięć więc byłoby 5N czyli O(N) ??

Proszę o pomoc


(Pablo_Wawa) #4

Tak, masz rację, jest podwójnie zagnieżdżona pętla (na końcu). Jakoś ją przeoczyłem.

Czyli pewnie jest O(N^2).


(Ragnar) #5

Na innym forum ktoś mi podał, że to będzie złożoność O(N*M) ale nie wiem czy stosuje się w ogóle taki zapis ?


(Pablo_Wawa) #6

No tak, jeśli mamy zwie zmienne N i M, to złożoność zapewne może być taka.