Co to jest dokładnie ta złożoność obliczeniowa?

pytanie zadane 11 stycznia 2020 w Rozwój zawodowy, nauka, praca przez jared Gaduła (3,600 p.)
zamknięte 14 stycznia 2020 przez jared

Wszędzie mówi się o złożoności obliczeniowej, że jest pesymistyczna, oczekiwana oraz optymistyczna, ale co to dokładnie jest? Służy do oceny algorytmów, ale co to formalnie jest? Jak to wyjaśnić?

komentarz zamknięcia: zamykam, bo nie ma sensu trzymać otwarte

komentarz 11 stycznia 2020 przez mokrowski Mędrzec (155,460 p.)

Nie obraź się... ale najlepiej w wyszukiwarce i zapytać nieco precyzyjniej. Inaczej pełna odpowiedź wymagała by wykładu na co najczęściej nie ma miejsca i czasu.

Zacznij od złożoności algorytmów: https://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa

Zerknij na podstawowe klasy złożoności (losowy wykres): http://vaxxxa.github.io/talks/introduction.to.algorithms-computational.complexity/static/images/big-o-complexity.png

... i wtedy zapytaj jak będziesz wiedział dokładnie czego nie rozumiesz.

Jeśli chcesz, polecę literaturę.

komentarz 11 stycznia 2020 przez jared Gaduła (3,600 p.)

Ale prostymi słowami co to jest? Funkcja, która określa zapotrzebowanie czasu w zależności od wprowadzonych danych wejściowych?

Bo takie wytłumaczenia jak

Złożoność obliczeniowa algorytmu – ilość zasobów komputerowych potrzebnych do jego wykonania:

Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych.

to co one mówią? Że złożoność obliczeniowa zajmuje się określaniem potrzebnych zasobów komputerowych do rozwiązania jakiegoś zadania/algorytmu. Skoro podałeś wykresy są to jakieś funkcje? Sory, że tak filozofuje, ale męczą mnie co rusz dziwne tłumaczenia w jakichś artykułach i prezentacjach.

Ja złożoność obliczeniową rozumiem jako funkcję o której wspomniałem, ale czy rzeczywiście tak jest?

1 odpowiedź

odpowiedź 11 stycznia 2020 przez adam_jankowski Mądrala (5,970 p.)

Jest to stosunek wielkości danych wejściowych do szybkości działania algorytmu

komentarz 11 stycznia 2020 przez tkz Nałogowiec (42,000 p.)

To jest asymptotyczne tempo wzrostu. Potocznie Notacja dużego O. Ilość zasobów niezbędnych do wykonania algorytmu można rozumieć jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej czy też złożoności pamięciowej.

komentarz 12 stycznia 2020 przez spamator12 Nałogowiec (28,230 p.)

ta, nalezy jeszcze przyjac ze niektore obliczenia (np funkcje) rosna wykladniczo, a wiec zuzycie mocy obliczeniowej zwieksza sie w czasie (rosnie trudnosc) co mzona tez zapisac poprzez wiekszy blad algorytmu albo jego dluzsza prace.