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

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?

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.

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

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

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.

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.

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

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