Jak zrozumieć O(n)

0

Co to jest notacja Big O? Czy używasz tego?

Chyba przegapiłem te zajęcia na uniwersytecie i nie mogę tego pojąć

Podczas nauki jednego z języków programowania natknąłem się na
Oznacza to, że obliczenie rozmiaru listy ma złożoność O(n). Z tego powodu dodawanie elementów na początku jest zwykle szybsze niż dołączanie na koniec listy:

Czy ktoś to używa i podałby przykłady z życia wzięte?

1

W Internecie znajdziesz sporo, ale otwórz sobie dowolny podręcznik do algorytmów i tam, notacja asymptotyczna jest tłumaczona na pierwszych stronach.

10

Definicje bez problemu znajdziesz w sieci - jak również rozróżnienie na złożoności optymistyczne, pesymistyczne, oczekiwane, jak wyznaczać złożoność itd.

Na chłopski rozum złożoność obliczeniowa mówi, jak szybko czas rozwiązania (jako liczba operacji) danego rodzaju zadania (np. dodanie elementu na koniec listy) rośnie ze wzrostem rozmiaru zadania (czyli rozmiaru danych na wejściu, N).

Jeśli masz O(n) to znaczy, że w miarę jak rosną dane wejściowe (np. dodajesz coś na koniec coraz większej listy) rośnie czas obliczeń - w tym przypadku liniowo, bo przejście od początku do końca listy (by tam coś dodać) wymaga N przejść.

Gdyby jakieś zadanie miało złożoność O(1) (np. uzyskanie dostępu do elementu tablicy, a nie linked list) to by znaczyło, że czas rozwiązania zasadniczo nie zależy od rozmiaru danych

Złożoność O(logn) (np. dla wyszukiwania binarnego) oznacza, że relacja między czasem obliczeń a rozmiarem zadania jest logarytmiczna. W przypadku wyszukiwania binarnego - ponieważ dzielisz coraz mniejsze połówki i połówki połówek etc. aż trafisz na szukany element lub zyskasz pewność, że go nie ma, to liczba kroków jest ograniczona do log(n).

0

Dzięki Panowie za wytłumaczenie - już rozumiem.

1 użytkowników online, w tym zalogowanych: 0, gości: 1