Informatyka UJ forum

Makros

Mam mały problem dotyczący złożoności obliczeniowej, a tak dokładniej to z algorytmami o złożoności logarytmicznej... Niech no mi ktoś powie, poczym, moge poznać, że jakiś algorytm jest tejże złożoności a nie np. kwadratowej...? może jakieś krótkie przykłady z omówieniem, czym to się chrakteryzuje...

---edit---

no i czemu do jasnej.... w tym przykładzie:

exe · Gość

No ja to tak robie: Wieceej to niz n, mniej niz n^2, jakies mnozenia sa, zatem bedzie n log n :P Oznacza to, ze dla n = 10, wykonanych zostanie ~ 10*lg 10 iteracji wewnetrznej petli. samo lg n masz czesto przy jakis drzewach, grafach, wyszukiwaniu binarnym itp itd. (lg to log o podstawie 2).

To tak na chlopski rozum, dokladniej, precyzyjniej masz w notatkach z wykladu :P

jagm

log n to znaczy, ze z kazdym wykonaniem pętli jesteś dwa razy bliżej końca niż poprzednio ;]
przykładem jest wyszukiwanie połówkowe:
jak masz n elementów, to przy każdym sprawdzeniu, czy a[(L+R)/2] to nasz szukany x, ilość elementów do sprawdzenia zmniejsza się o około połowę.