Przegląd
Inni podali dobre przykłady diagramów, takie jak diagramy drzewiaste. Nie widziałem żadnych prostych przykładów kodu. Oprócz mojego wyjaśnienia przedstawię kilka algorytmów z prostymi instrukcjami drukowania, aby zilustrować złożoność różnych kategorii algorytmów.
Po pierwsze, będziesz chciał mieć ogólne pojęcie o logarytmie, które możesz uzyskać na stronie https://en.wikipedia.org/wiki/Logarithm . Zastosowanie w naukach przyrodniczych ei dziennik naturalny. Uczniowie inżynierii używają log_10 (log log base 10), a informatycy często używają log_2 (log base 2), ponieważ komputery są binarne. Czasami zobaczysz skróty logu naturalnego, ponieważ ln()inżynierowie zwykle wyłączają _10 i po prostu używają, log()a log_2 to skrót lg(). Wszystkie rodzaje logarytmów rosną w podobny sposób, dlatego dzielą tę samą kategorię log(n).
Gdy spojrzysz na poniższe przykłady kodu, polecam przyjrzenie się O (1), następnie O (n), a następnie O (n ^ 2). Kiedy będziesz z nimi dobry, spójrz na innych. Podałem czyste przykłady, a także odmiany, aby zademonstrować, jak subtelne zmiany mogą nadal prowadzić do tej samej kategoryzacji.
Możesz myśleć o O (1), O (n), O (logn) itp. Jako klasach lub kategoriach wzrostu. Niektóre kategorie zajmą więcej czasu niż inne. Te kategorie pomagają nam uporządkować wydajność algorytmu. Niektóre rosły szybciej wraz ze wzrostem wartości wejściowej n. Poniższa tabela pokazuje wspomniany wzrost liczbowo. W poniższej tabeli traktuj log (n) jako pułap log_2.
Proste przykłady kodów różnych dużych kategorii O:
O (1) - Przykłady stałych czasów:
Algorytm 1 wypisuje cześć raz i nie zależy od n, więc zawsze będzie działał w stałym czasie, więc tak jest O(1).
print "hello";
Algorytm 2 drukuje cześć 3 razy, jednak nie zależy to od wielkości wejściowej. Nawet gdy rośnie n, ten algorytm zawsze drukuje tylko cześć 3 razy. To powiedziawszy 3, jest stałą, więc ten algorytm też O(1).
print "hello";
print "hello";
print "hello";
O (log (n)) - Przykłady logarytmiczne:
- Algorytm 3 - Działa jak „log_2”
Algorytm 3 pokazuje algorytm działający w log_2 (n). Zauważ, że operacja końcowa pętli for zwielokrotnia bieżącą wartość i przez 2, więc izmienia się od 1 do 2 do 4 do 8 do 16 do 32 ...
for(int i = 1; i <= n; i = i * 2)
print "hello";
- Algorytm 4 - Działa jak „log_3”
Algorytm 4 pokazuje log_3. Uwaga izmienia się z 1 na 3 na 9 na 27 ...
for(int i = 1; i <= n; i = i * 3)
print "hello";
- Algorytm 5 - Działa jak „log_1.02”
Algorytm 5 jest ważny, ponieważ pomaga pokazać, że dopóki liczba jest większa niż 1, a wynik jest wielokrotnie mnożony względem siebie, patrzysz na algorytm logarytmiczny.
for(double i = 1; i < n; i = i * 1.02)
print "hello";
O (n) - Przykłady czasu liniowego:
Ten algorytm jest prosty, który drukuje cześć n razy.
for(int i = 0; i < n; i++)
print "hello";
Ten algorytm pokazuje odmianę, w której wypisze cześć n / 2 razy. n / 2 = 1/2 * n. Ignorujemy stałą 1/2 i widzimy, że ten algorytm to O (n).
for(int i = 0; i < n; i = i + 2)
print "hello";
O (n * log (n)) - nlog (n) Przykłady:
Pomyśl o tym jako o połączeniu O(log(n))i O(n). Zagnieżdżanie pętli for pomaga nam uzyskaćO(n*log(n))
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j = j * 2)
print "hello";
Algorytm 9 jest podobny do algorytmu 8, ale każda z pętli dopuszcza wariacje, które nadal powodują, że końcowy wynik jest O(n*log(n))
for(int i = 0; i < n; i = i + 2)
for(int j = 1; j < n; j = j * 3)
print "hello";
O (n ^ 2) - n do kwadratu Przykłady:
O(n^2) można łatwo uzyskać poprzez zagnieżdżenie standardu dla pętli.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
Jak algorytm 10, ale z pewnymi odmianami.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j = j + 2)
print "hello";
O (n ^ 3) - n pokrojone w kostkę Przykłady:
To jest jak algorytm 10, ale z 3 pętlami zamiast 2.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
print "hello";
Jak algorytm 12, ale z pewnymi odmianami, które wciąż dają O(n^3).
for(int i = 0; i < n; i++)
for(int j = 0; j < n + 5; j = j + 2)
for(int k = 0; k < n; k = k + 3)
print "hello";
Podsumowanie
Powyżej podano kilka prostych przykładów i odmian, aby pokazać, jakie subtelne zmiany można wprowadzić, które tak naprawdę nie zmieniają analizy. Mam nadzieję, że daje to wystarczającą wiedzę.
