• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność Algorytmów

Object Storage Arubacloud
0 głosów
367 wizyt
pytanie zadane 1 lutego 2018 w C i C++ przez Pachucki Nowicjusz (120 p.)
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

2 odpowiedzi

0 głosów
odpowiedź 1 lutego 2018 przez Wiciorny Ekspert (272,110 p.)
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
1
komentarz 1 lutego 2018 przez jankustosz1 Nałogowiec (35,940 p.)
Jeszcze jedna ważna rzecz to rozpatrywać zawsze najgorszy, najdurniejszy przypadek.
komentarz 1 lutego 2018 przez Wiciorny Ekspert (272,110 p.)
dokładnie to masz racje z warunku "notacji O"
0 głosów
odpowiedź 1 lutego 2018 przez jankustosz1 Nałogowiec (35,940 p.)
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.

Podobne pytania

0 głosów
1 odpowiedź 1,001 wizyt
pytanie zadane 6 grudnia 2017 w C i C++ przez blacktiger23 Nowicjusz (160 p.)
0 głosów
1 odpowiedź 328 wizyt
pytanie zadane 14 czerwca 2021 w Algorytmy przez Tanormalnie Użytkownik (550 p.)
0 głosów
2 odpowiedzi 398 wizyt
pytanie zadane 5 grudnia 2019 w Algorytmy przez progNewbie Obywatel (1,130 p.)

92,674 zapytań

141,575 odpowiedzi

320,045 komentarzy

62,038 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...