Jestem programistą i właśnie zacząłem czytać Algorytmy. Nie jestem do końca przekonany zapisami, a mianowicie Bog Oh, Big Omega i Big Theta. Powodem jest z definicji Big Oh, stwierdza ona, że powinna istnieć funkcja g (x) taka, aby zawsze była większa lub równa f (x). Lub f (x) <= cn dla wszystkich wartości n> n0.
Dlaczego nie wspominamy o stałej wartości w definicji? Na przykład, powiedzmy funkcję 6n + 4, oznaczamy ją jako O (n). Ale nie jest prawdą, że definicja obowiązuje dla całej stałej wartości. Ma to zastosowanie tylko wtedy, gdy c> = 10 i n> = 1. Dla mniejszych wartości c niż 6, wartość n0 wzrasta. Dlaczego więc nie wspominamy o stałej wartości jako części definicji?
big-o
algorithm-analysis
Pradeep
źródło
źródło
Odpowiedzi:
Jest kilka powodów, ale prawdopodobnie najważniejszym jest to, że stałe są funkcją implementacji algorytmu, a nie sam algorytm. Kolejność algorytmów jest przydatna do porównywania algorytmów niezależnie od ich implementacji.
Rzeczywisty czas działania Quicksort zwykle zmienia się, jeśli jest zaimplementowany w C, Python, Scala lub Postscript. To samo dotyczy sortowania bąbelkowego - środowisko wykonawcze będzie się znacznie różnić w zależności od implementacji.
Jednak to, co się nie zmieni, to fakt, że gdy wszystko inne jest równe, ponieważ zestaw danych staje się większy, czas wymagany do uruchomienia sortowania bąbelkowego wzrośnie szybciej niż czas wymagany do uruchomienia szybkiego sortowania w typowym przypadku, bez względu na język lub maszynę są wdrażane przy założeniu, że implementacja jest właściwie poprawna. Ten prosty fakt pozwala na inteligentne wnioskowanie na temat samych algorytmów, gdy konkretne szczegóły nie są dostępne.
Zamówienie od An filtrów algorytmu spośród czynników, które są ważne w rzeczywistych pomiarów rzeczywistych, mają tendencję do być tylko hałas podczas porównywania algorytmów w sposób abstrakcyjny.
źródło
O (n) i inna notacja porządkowa (zazwyczaj) nie dotyczy zachowania funkcji dla małych wartości. Dotyczy zachowania funkcji dla bardzo dużych wartości, a mianowicie granic, gdy n przesuwa się w kierunku nieskończoności.
Stałe technicznie mają znaczenie, ale są zwykle wyodrębniane, gdy n staje się wystarczająco duży, wartość c jest całkowicie nieistotna. Jeśli wartość c jest ważna, możemy ją uwzględnić w analizie, ale jeśli porównywane funkcje nie mają bardzo dużych stałych współczynników lub jeśli wydajność jest szczególnie istotną kwestią, zazwyczaj nie są.
źródło
Notacja Big O zgodnie z definicją stwierdza, że: Notacja Big O opiera się na intuicji, że dla wszystkich wartości nw i na prawo od n 'wartość f (n) jest równa lub mniejsza niż cg (n). Stałe również nie mają znaczenia, kiedy przechodzisz do czynników o wysokiej wartości (zmiennych) (takich jak n-kwadrat lub n-sześcian), ponieważ są one tylko stałymi, a nie zmiennymi wielkościami, które mogą stać się tak duże jak te czynniki. Poniżej znajduje się wykres notacji Big-O.
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}
Istotą tego zapisu jest fakt, że „
how lower is f(n) from c.g(n) and not when it starts becoming lower
”.źródło
W analizie algorytmów porządek wzrostu jest kluczową abstrakcją i daje szybkość, z jaką zmienia się czas działania wraz ze zmianą wielkości wejściowej. Powiedzmy, że algorytm ma czas działania
f(n) = 2n + 3
. Teraz podłączamy jakiś rozmiar wejściowy,Jak widać, kolejność wzrostu zależy głównie od zmiennej
n
; stałe 2 i 3 są mniej znaczące, a wraz ze wzrostem wielkości wejściowej stają się jeszcze mniej znaczące w jej określaniu. Dlatego w analizie algorytmów stałe są pomijane na korzyść zmiennej określającej kolejność wzrostu funkcji.źródło
Całe pojęcie notacji Big-Oh polega na ignorowaniu stałych i przedstawianiu najważniejszej części funkcji opisującej czas działania algorytmu.
Zapomnij na chwilę o formalnej definicji. Która jest gorsza (szybciej rosnąca) funkcja
n^2 - 5000
lub5000 n + 60000
? Dlan
mniej niż około 5000 funkcja liniowa jest większa (a przez to gorsza). Poza tym (dokładna wartość 5013?) Równanie kwadratowe jest większe.Ponieważ jest więcej (o kilka więcej) liczb dodatnich większych niż 5000 niż mniej, przyjmujemy, że kwadrat jest ogólnie „większą” (gorszą) funkcją. Zapis kolejności (Big-Oh itp.) Wymusza to (zawsze można wyeliminować dodatek i stałą multiplikatywną za pomocą tych definicji).
Oczywiście rzeczy nie zawsze są proste. Czasami można nie chcą wiedzieć, tych stałych. Który jest lepszy sortowanie wstawiane lub sortowanie bąbelkowe? Oba są
O(n^2)
. Ale jedno naprawdę jest lepsze od drugiego. Dzięki bardziej szczegółowej analizie można uzyskać stałe, o których się zastanawiasz. Zwykle o wiele łatwiej jest obliczyć funkcję Big-Ohha niż funkcję bardziej dokładną.Big-Oh ignoruje te stałe, aby uprościć i ułatwić najważniejsze porównania. Lubimy notację, ponieważ zwykle nie chcemy wiedzieć o (najczęściej nieistotnych) stałych.
źródło
(ponieważ jest to dłuższa odpowiedź, przeczytaj pogrubienie w celu podsumowania )
Weźmy twój przykład i przejdźmy go krok po kroku, rozumiejąc cel tego, co robimy. Zaczynamy od twojej funkcji i celu znalezienia jej notacji Big Oh:
Po pierwsze, niech
O(g(n))
będzie zapis Big Oh, którego szukamyf(n)
. Z definicji Big Oh, musimy znaleźć uproszczone, wg(n)
którym istnieją pewne stałec
in0
gdziec*g(n) >= f(n)
jest prawdziwe dla wszystkichn
większych niżn0
.Najpierw wybierzmy
g(n) = 6n + 4
(który dałbyO(6n+4)
w Big Oh). W tym przypadku widzimy, żec = 1
każda wartośćn0
spełni wymagania matematyczne z naszej definicji Big Oh, ponieważg(n)
zawsze jest równaf(n)
:W tym momencie spełniliśmy wymagania matematyczne. Gdybyśmy się zatrzymali
O(6n+4)
, jasne jest, że nie jest to bardziej pomocne niż pisanief(n)
, więc pominęłoby to prawdziwy cel notacji Big Oh: zrozumieć ogólną złożoność czasową algorytmu! Przejdźmy zatem do następnego kroku: uproszczenia.Po pierwsze, czy możemy uprościć
6n
tak wielką Big OhO(4)
? Nie! (Ćwicz dla czytelnika, jeśli nie rozumie dlaczego)Po drugie, czy możemy uprościć
4
tak, aby Big Oh byłO(6n)
? Tak! W takim przypadkug(n) = 6n
:W tym momencie wybierzmy
c = 2
od tego czasu lewa strona będzie rosła szybciej (o 12) niż prawa strona (o 6) dla każdego przyrostun
.Teraz musimy znaleźć dodatnią,
n0
gdzie powyższe równanie jest prawdziwe dla wszystkichn
większych niż ta wartość. Ponieważ wiemy już, że lewa strona rośnie szybciej niż prawa, wszystko, co musimy zrobić, to znaleźć jedno pozytywne rozwiązanie. Zatem, ponieważn0 = 2
sprawia, że powyższa prawda jest prawdą, wiemy o tymg(n)=6n
lubO(6n)
jest to potencjalna notacja Big Ohf(n)
.Czy możemy uprościć
6
tak, aby Big Oh byłO(n)
? Tak! W takim przypadkug(n) = n
:Wybierzmy,
c = 7
ponieważ lewa zwiększy się szybciej niż prawa.Widzimy, że powyższe będzie prawdziwe dla wszystkich
n
większych lub równychn0 = 4
. ZatemO(n)
potencjalna notacja Big Ohf(n)
. Czy możemyg(n)
już uprościć ? Nie!Wreszcie stwierdziliśmy, że najprostszą notacją Big Oh
f(n)
jestO(n)
. Dlaczego przez to wszystko przeszliśmy? Ponieważ teraz wiemy, żef(n)
jest liniowy , ponieważ jego notacja Big Oh ma liniową złożonośćO(n)
. Zaletą jest to, że teraz możemy porównać złożoność czasową zf(n)
innymi algorytmami! Na przykład, teraz wiemy, żef(n)
jest porównywalny do czasu złożoności funkcjih(n) = 123n + 72
,i(n) = n
,j(n) = .0002n + 1234
, etc; ponieważ stosując ten sam proces uproszczenia opisany powyżej, wszystkie mają liniową złożoność czasową wynoszącąO(n)
.Słodkie!!!
źródło
O(4)
, to sprawi, że nasze równanie nierównościc*4 >= 6n+4
, i dla każdego,c
który wybraliśmy, zawsze możemy znaleźć wartość, w której wszystkie wartościn
powyżej, które spowodują, że nierówność będzie fałszywa.c
in0
nie są ważne. To, co JEST ważne,n0
istnieje dla tych,c
których wybieramy. Aby było to prawdą, lewa strona nierówności musi rosnąć szybciej niż prawa strona dla dużych wartościn
.c=6
nie nadaje się do tego (6n >= 6n+4
nigdy nie jest prawdą), więc wybrałemc=7
. Mógłbym równie dobrze wybrałc=10
,c=734
alboc=6.0000001
i nadal były w stanie zobaczyć, że nie było pewnen0
, że istniał, aby nierówność odnosi się don >= n0
, co oznacza, że Big O testujemy jest prawidłowy.Jeśli masz funkcję wydajności
6n + 4
, odpowiednie pytanie brzmi: „6 czego?”. Jak powiedział jeden komentarz: co reprezentuje twoja stała? Z fizyki, jakie są jednostki twojego stałego czynnika?Powodem, dla którego notacja O () jest tak szeroko stosowana do opisywania wydajności algorytmu, jest to, że nie ma przenośnego sposobu na odpowiedź na to pytanie. Różne procesory będą potrzebowały różnej liczby cykli zegara i różnej ilości czasu, aby wykonać to samo obliczenie elementarne, lub mogą inaczej zbić odpowiednie obliczenia elementarne. Różne języki komputerowe lub różne opisy formalne i nieformalne, takie jak pseudokod, będą reprezentować algorytmy w sposób trudny do bezpośredniego porównania. Nawet implementacje w tym samym języku mogą reprezentować ten sam algorytm na różne sposoby - trywialne szczegóły formatowania, takie jak liczba linii poza tym, generalnie będziesz mieć szeroki wybór dowolnych strukturalnych wyborów do implementacji dowolnego algorytmu.
Spójrz na to z innej strony: używamy „algorytmu” nie do opisania konkretnej implementacji, ale do opisania całej klasy potencjalnych implementacji tej samej ogólnej procedury. Ta abstrakcja ignoruje szczegóły implementacji na rzecz udokumentowania czegoś o wartości ogólnej, a stały współczynnik wydajności jest jednym z tych szczegółów.
To powiedziawszy, opisom algorytmów często towarzyszy folklor, notatki, a nawet rzeczywiste testy porównawcze opisujące wydajność rzeczywistych implementacji na rzeczywistym sprzęcie. Daje to przybliżone pojęcie, jakiego rodzaju stałego czynnika można się spodziewać, ale należy go również wziąć z odrobiną soli, ponieważ rzeczywista wydajność zależy od rzeczy, takich jak nakład pracy włożony w optymalizację danej implementacji. W dłuższej perspektywie względna wydajność porównywalnych algorytmów ma tendencję do dryfowania wraz ze zmianą architektury najnowszych i największych procesorów ...
źródło