Złożoność Algorytmów

Question

Witam,

Często w pytaniach ABCD pojawiają się pytania o złożoność algorytmu. Przeważnie wygląda to tak, że jest podany kod i my mamy podać jaka jest złożoność algorytmu np O(n^2), O(Logn).

I teraz rodzi się pytanie jak mogę oszacować, złożoność, za pomocą kartki + długopisu w krótkim (przeważnie 1 minutowym) czasie? Ma ktoś radę jak to robić?

 

Pozdrawiam

Answer 1

1. n- załóżmy jest liczbą danych - operacji

2. zliczasz liczbę operacji na "określonych danych"  tzn badając stosunek ilości danych do operacji na szybciora

3. Zliczasz do momentu kiedy algoryt,- zachodzi tzn. uzyskujemy rozwiązanie

4. i sprawdzasz jak szybko rosną te operacje ... dodając dane czy szybciej niż wykres logarytmu czy szybciej niz n^2 itd...

Niestety pewne rzeczy musisz znać... tak samo znać pewne algorytmy na pamięc etc. To są rzeczy które programiści znać powinni, tak jak liczenie miejsca zerowego w matematyce etc.

Więc liczyć kwadraty, wzory logarytmiczne, znać wykresy to musisz umieć zawsze

Comments

Jeszcze jedna ważna rzecz to rozpatrywać zawsze najgorszy, najdurniejszy przypadek.

---

dokładnie to masz racje z warunku "notacji O"

Answer 2

Moim zdaniem nie jest ci potrzebna kartka. Wystarczy przeanalizować kod. Widzisz że jest pętla od 1 do n no to masz złożoność n. W środku tej pętli masz np. jakiegoś binsearcha w złożoności log n no to znaczy że z każdym obiegiem pętli odbędzie się dodatkowo ta operacja więc złożoność to O(n*logn). Proste to jest, oczywiście jeszcze musisz zwrócić uwagę na jakiś warunki itp.