Notacja Big Oh nie wspomina o stałej wartości

13

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?

Pradeep
źródło
4
Jak proponujesz dokładnie przedstawić stałą wartość?
Daniel B
1
Idąc dalej o krok dalej, dowolną funkcją kończącą jest O (1), jeśli związałeś n.
Brian

Odpowiedzi:

23

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.

tylerl
źródło
22

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ą.

Inżynier świata
źródło
3
Na przykład budowanie piramid to O (n), sortowanie ich zdjęć to O (n log n) - w pewnym momencie możesz mieć tyle piramid, że sortowanie zdjęć zajęłoby więcej czasu niż zbudowanie nowego! Ale tylko dla bardzo dużej liczby piramid!
Martin Beckett
Dobra odpowiedź, ale dla danego N i dwóch algorytmów, które zwykle należą do tej samej „rodziny” złożoności, uzasadnione może być robienie dokładnie tego, co sugeruje PO i uwzględnienie przynajmniej względnych współczynników. Algorytm liniowy z podwójną liczbą instrukcji na element w stosunku do innego może być nazwany * O * (2N) do drugiego alg * O * (N), aby pokazać różnicę względną, ponieważ dla dowolnego N pierwszy algorytm będzie zawsze podwójny czas wykonania drugiego; jednak w porównaniu do funkcji z innej rodziny złożoności, takiej jak * O * (NlogN), współczynniki nie mają znaczenia.
KeithS,
10

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'}




wprowadź opis zdjęcia tutaj

Istotą tego zapisu jest fakt, że „ how lower is f(n) from c.g(n) and not when it starts becoming lower”.

Vaibhav Agarwal
źródło
W takim przypadku dla każdego O (n) jest również Big theta n, ponieważ zgodnie z definicją dla pewnej stałej będzie to dolna granica, a dla niektórych stałych górna granica. na przykład 6n + 4 jest również dużą theta (n), ponieważ gdy c jest mniejsze niż 10, zawsze jest to dolna granica. a gdy c jest większe niż 10, jest to górna granica. Czy możemy więc powiedzieć, że dla dowolnej notacji Big Oh jest również Big theta?
Pradeep
1
Mówisz to na odwrót: „Big Theta znaczy Big Oh”. A Big-Oh można zastąpić Big-Theta dla asymptotycznie ciasnych granic.
Vaibhav Agarwal
9

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,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

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.

theD
źródło
1

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 - 5000lub 5000 n + 60000? Dla nmniej 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.

Mitch
źródło
1

(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:

f(n) = 6n+4

Po pierwsze, niech O(g(n))będzie zapis Big Oh, którego szukamy f(n). Z definicji Big Oh, musimy znaleźć uproszczone, w g(n) którym istnieją pewne stałe ci n0gdzie c*g(n) >= f(n)jest prawdziwe dla wszystkich nwiększych niż n0.

Najpierw wybierzmy g(n) = 6n + 4(który dałby O(6n+4)w Big Oh). W tym przypadku widzimy, że c = 1każda wartość n0spełni wymagania matematyczne z naszej definicji Big Oh, ponieważ g(n)zawsze jest równa f(n):

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

W tym momencie spełniliśmy wymagania matematyczne. Gdybyśmy się zatrzymaliO(6n+4) , jasne jest, że nie jest to bardziej pomocne niż pisanie f(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ć 6ntak wielką Big Oh O(4)? Nie! (Ćwicz dla czytelnika, jeśli nie rozumie dlaczego)

Po drugie, czy możemy uprościć 4tak, aby Big Oh był O(6n)? Tak! W takim przypadku g(n) = 6n:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

W tym momencie wybierzmy c = 2od tego czasu lewa strona będzie rosła szybciej (o 12) niż prawa strona (o 6) dla każdego przyrostu n.

2*6n      >=  6n + 4

Teraz musimy znaleźć dodatnią, n0gdzie powyższe równanie jest prawdziwe dla wszystkich nwię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 = 2sprawia, że ​​powyższa prawda jest prawdą, wiemy o tym g(n)=6nlub O(6n)jest to potencjalna notacja Big Oh f(n).

Czy możemy uprościć 6tak, aby Big Oh był O(n)? Tak! W takim przypadku g(n) = n:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Wybierzmy, c = 7ponieważ lewa zwiększy się szybciej niż prawa.

7*n         >=  6n + 4

Widzimy, że powyższe będzie prawdziwe dla wszystkich nwiększych lub równych n0 = 4. Zatem O(n)potencjalna notacja Big Oh f(n). Czy możemy g(n)już uprościć ? Nie!

Wreszcie stwierdziliśmy, że najprostszą notacją Big Oh f(n)jest O(n). Dlaczego przez to wszystko przeszliśmy? Ponieważ teraz wiemy, że f(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ą z f(n)innymi algorytmami! Na przykład, teraz wiemy, że f(n)jest porównywalny do czasu złożoności funkcji h(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!!!

Briguy37
źródło
Cześć, dobre wyjaśnienie. Nadal mam kilka wątpliwości. 1. Nie możemy zrobić 6n + 4 jako O (4), ponieważ istnieje zmienna wartość „n”. Czy to jest odpowiedź? 2. podczas uproszczenia wybrałeś c = 7 i odpowiednio wyliczyłeś n0 do 4. Co skłoniło cię do podjęcia decyzji c = 7 i nie mniej niż 7? ponieważ w oparciu o wartość c zmieni się n0.
Pradeep
@ Pradeep: Dla 1 masz rację. Dla głębszego wyjaśnienia: jeśli spróbujemy O(4), to sprawi, że nasze równanie nierówności c*4 >= 6n+4, i dla każdego, cktóry wybraliśmy, zawsze możemy znaleźć wartość, w której wszystkie wartości npowyżej, które spowodują, że nierówność będzie fałszywa.
Briguy37,
@ Pradeep: Dla 2 rzeczywiste wartości ci n0nie są ważne. To, co JEST ważne, n0istnieje dla tych, cktórych wybieramy. Aby było to prawdą, lewa strona nierówności musi rosnąć szybciej niż prawa strona dla dużych wartości n. c=6nie nadaje się do tego ( 6n >= 6n+4nigdy nie jest prawdą), więc wybrałem c=7. Mógłbym równie dobrze wybrał c=10, c=734albo c=6.0000001i nadal były w stanie zobaczyć, że nie było pewne n0, że istniał, aby nierówność odnosi się do n >= n0, co oznacza, że Big O testujemy jest prawidłowy.
Briguy37
Dziękuję za jasne wyjaśnienie. Właśnie tego dokładnie szukałem. Jeszcze raz dziękuję.
Pradeep
@Pradeep: Cieszę się, że mogłem pomóc :)
Briguy37
1

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 ...

nadchodząca burza
źródło