O (·) nie jest funkcją, więc w jaki sposób funkcja może być jej równa?

Całkowicie rozumiem, co oznacza duża notacjaMój problem polega na tym, że mówimy , gdzie jest czasem działania algorytmu na wejściu wielkości .$O$$T(n)=O(f(n))$$T(n)$$n$

Rozumiem semantykę tego. Ale i to dwie różne rzeczy.$T(n)$$O(f(n))$

$T(n)$ jest dokładną liczbą, ale nie jest funkcją, która wyrzuca liczbę, więc technicznie nie możemy powiedzieć, że równa się , jeśli ktoś zapyta Ci co to jest wartość od , jaka byłaby twoja odpowiedź? Nie ma odpowiedzi.$O(f(n))$$T(n)$ $O(f(n))$$O(f(n))$

Ściśle mówiąc, $O(f(n))$ jest zbiorem funkcji. Zatem wartość $O(f(n))$ jest po prostu zbiorem wszystkich funkcji, które rosną asymptotycznie nie szybciej niż $f(n)$ . Notacja $T(n) = O(f(n))$ to tylko konwencjonalny sposób zapisu, że $T(n) \in O(f(n))$ .

Zauważ, że wyjaśnia to również pewne zastrzeżenia notacjiNa przykład piszemy, że , ale nigdy nie piszemy, że . Cytując Donalda Knutha (Sztuka programowania komputerowego, 1.2.11.1):$O$$(1/2) n^2 + n = O(n^2)$$O(n^2)=(1/2)n^2 + n$

Najważniejszą kwestią jest koncepcja równości jednokierunkowej . [...] Jeśli i są formułami zawierającymi notację, wówczas notacja oznacza, że ​​zestaw funkcji oznaczonych przez jest zawarty w zestawie oznaczonym przez .$\alpha(n)$$\beta(n)$$O$$\alpha(n)=\beta(n)$$\alpha(n)$β ( n )$\beta(n)$

$O$ jest funkcją tj. akceptuje funkcję i daje zestaw funkcji, które dzielą asymptotyczną granicę (co najwyżej) . I ściśle mówiąc, poprawną notacją jest więc lub krótki ale zwyczajowo w matematyce, nauce i CS używa się zwyczajnie zmienna gdzieś w wyrażeniu, która oznacza, że ​​rozważasz funkcje argumentu po obu stronach. Więc jest również całkiem w porządku.

Odradzałbym pisanie , ale opinie są różne .$T(n) = O(f(n))$

Formalnie rzecz biorąc, jest zbiorem funkcji tak że dla pewnej stałej i wszystkie wystarczająco duże  . Zatem najbardziej pedantycznie dokładnym sposobem pisania byłoby . Jednak użycie zamiast  jest całkowicie standardowe, a oznacza po prostu . Zasadniczo nigdy nie jest to dwuznaczne, ponieważ prawie nigdy nie manipulujemy zbiorem .$O(f(n))$$g$$g(n)\leq k\,f(n)$$k$$n$$T(n)\in O(f(n))$$=$$\in$$T(n)=O(f(n))$$T(n)\in O(f(n))$$O(f(n))$

W pewnym sensie użycie równości powoduje, że oznacza „jakąś funkcję taką, że dla wszystkich wystarczająco dużych  ”, a to oznacza, że ​​możesz pisać takie rzeczy jak . Zauważ, że jest to o wiele dokładniejsze niż, np. lub .$O(f(n))$$g$$g(n)\leq f\,g(n)$$n$$f(n) = 3n + O(\log n)$$f(n)=\Theta(n)$$f(n)=O(n+\log n)$

Prolog: Duża notacja jest klasycznym przykładem potęgi i niejednoznaczności niektórych notacji jako części języka kochanego przez ludzki umysł. Bez względu na to, jak wiele zamieszania to spowodowało, wybór zapisu stanowi przekazanie pomysłów, które możemy łatwo zidentyfikować i na które zgodzimy się skutecznie.$O$

Całkowicie rozumiem, co oznacza duża notacjaMój problem polega na tym, że mówimy , gdzie jest czasem działania algorytmu na wejściu wielkości .$O$$T(n)=O(f(n))$$T(n)$$n$

Przepraszamy, ale nie masz problemu, jeśli rozumiesz znaczenie dużej notacji$O$

Rozumiem semantykę tego. Ale i to dwie różne rzeczy. jest dokładną liczbą, ale nie jest funkcją, która wyrzuca liczbę, więc technicznie nie możemy powiedzieć, że równa się , jeśli ktoś zapyta Ci co to jest wartość od , jaka byłaby twoja odpowiedź? Nie ma odpowiedzi.$T(n)$$O(f(n))$$T(n)$$O(f(n))$$T(n)$ O ( f ( n ) ) O ( f ( n ) ) $O(f(n))$$O(f(n))$

Ważna jest semantyka . Ważne jest (jak) ludzie mogą łatwo zgodzić się na jedną z jej precyzyjnych interpretacji, które opisają asymptotyczne zachowanie lub złożoność czasu lub przestrzeni, którymi jesteśmy zainteresowani. Domyślna precyzyjna interpretacja / definicja , zgodnie z tłumaczeniem z Wikipedii ,$T(n)=O(f(n))$

$T$ jest funkcją o wartości rzeczywistej lub zespolonej, a jest funkcją o wartościach rzeczywistych, obie zdefiniowane w pewnym nieograniczonym podzbiorze rzeczywistych liczb dodatnich, tak że jest ściśle dodatnie dla wszystkich wystarczająco dużych wartości . Dla wszystkich wystarczająco dużych wartości wartość bezwzględna jest co najwyżej dodatnią stałą wielokrotnością . Oznacza to, że istnieje dodatnia liczba rzeczywista i liczba rzeczywista taka, że$f$$f(n)$$n$$n$$T(n)$$f(n)$$M$$n_0$

${\text{ for all }n\geq n_{0}, |T(n)|\leq \;Mf(n){\text{ for all }}n\geq n_{0}.}$

Uwaga: ta interpretacja jest uważana za definicję . Wszelkie inne interpretacje i zrozumienia, które mogą ci bardzo pomóc na różne sposoby, są wtórne i następcze. Wszyscy (cóż, przynajmniej każdy tutaj odpowiadający) zgadza się na tę interpretację / definicję / semantykę. Tak długo, jak możesz zastosować tę interpretację, prawdopodobnie jesteś dobry przez większość czasu. Zrelaksuj się i bądź wygodny. Nie chcesz za dużo myśleć, tak jak nie myślisz za dużo o nieregularności języka angielskiego, francuskiego lub większości języków naturalnych. Wystarczy użyć zapisu według tej definicji.

$T(n)$O ( f ( n ) ) T ( n ) O ( f ( n ) ) O ( f ( n ) ) jest dokładną liczbą, ale nie jest funkcją, która wyrzuca liczbę, więc technicznie nie możemy powiedzieć, że równa się , jeśli ktoś zapyta Ci co to jest wartość od , jaka byłaby twoja odpowiedź? Nie ma odpowiedzi.$O(f(n))$$T(n)$ $O(f(n))$$O(f(n))$

Rzeczywiście, nie ma odpowiedzi, ponieważ pytanie jest źle postawione. nie oznacza dokładnej liczby. Ma oznaczać funkcję o nazwie i której parametrem formalnym jest (co jest w pewnym sensie ograniczone do in ). Jest to tak samo poprawne, a tym bardziej, jeśli napiszemy . Jeśli jest funkcją odwzorowującą do a jest funkcją odwzorowującą do , konwencjonalne jest również zapisywanie lub$T(n)$$T$$n$$n$$f(n)$$T=O(f)$$T$$n$$n^2$$f$$n$$n^3$$f(n)=O(n^3)$$n^2=O(n^3)$O. Należy również pamiętać, że definicja nie mówi, że jest funkcją, czy nie. Nie mówi wcale, że lewa strona powinna być w ogóle równa prawej stronie! Masz rację, podejrzewając, że znak równości nie oznacza równości w jej zwykłym znaczeniu , w którym możesz zmienić obie strony równości i powinna być poparta równoważną relacją. (Innym jeszcze bardziej znanym przykładem nadużycia znaku równości jest użycie znaku równości w celu przypisania w większości języków programowania, zamiast bardziej kłopotliwego, jak w niektórych językach).$O$:=

Jeśli martwimy się tylko o tę jedną równość (również zaczynam nadużywać języka. To nie jest równość ; jednak jest to równość, ponieważ w zapisie znajduje się znak równości lub można ją interpretować jako pewien rodzaj równości ), , ta odpowiedź jest gotowa.$T(n)=O(f(n))$

Jednak pytanie faktycznie trwa. Co to znaczy, na przykład, ? Ta równość nie jest objęta powyższą definicją. Chcielibyśmy wprowadzić kolejną konwencję, konwencję zastępczą . Oto pełne oświadczenie o konwencji zastępczej, jak podano w Wikipedii .$f(n)=3n+O(\log n)$

W bardziej skomplikowanym użyciu może występować w różnych miejscach równania, nawet kilka razy z każdej strony. Na przykład następujące są prawdziwe dla .$O(\cdots)$$n\to \infty$

$(n+1)^{2}=n^{2}+O(n)$
$(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$
$n^{O(1)}=O(e^{n})$

Znaczenie takich instrukcji jest następujące: dla wszystkich funkcji, które spełniają każde po lewej stronie, są pewne funkcje spełniające każde po prawej stronie, takie jak podstawienie wszystkich tych funkcji do równania wyrównuje obie strony. Na przykład trzecie równanie powyżej oznacza: „Dla dowolnej funkcji istnieje funkcja taka, że . ”$O(\cdots)$$O(\cdots)$$f(n) = O(1)$$g(n) = O(e^n)$$n^{f(n)} = g(n)$

Możesz tu sprawdzić inny przykład konwencji symbolu zastępczego w akcji.

Być może zauważyliście już, że nie użyłem teoretycznego wyjaśnienia dużej adnotacji. Wszystko, co zrobiłem, to po prostu pokazać, nawet bez wyjaśnienia teoretycznego, takiego jak „ jest zbiorem funkcji”, wciąż możemy w pełni i doskonale zrozumieć dużą adnotację. Jeśli uznasz, że to teoretyczne wyjaśnienie jest przydatne, idź dalej.$O$$O(f(n))$$O$

Możesz sprawdzić sekcję „notacja asymptotyczna” CLRS, aby uzyskać bardziej szczegółowy wzorzec analizy i użycia dla rodziny notacji dla zachowania asymptotycznego, takiego jak duże , , małe , małe , użycie wielu zmiennych i więcej. Wpis Wikipedia jest także całkiem dobre referencje.$\Theta$$\Omega$$o$$\omega$

Wreszcie istnieje pewna niejednoznaczność / kontrowersje związane z dużą notacją z wieloma zmiennymi 1 i 2 . Możesz zastanowić się dwa razy, kiedy ich używasz.$O$

W Podręczniku projektowania algorytmów [1] można znaleźć akapit na ten temat:

Notacja Big Oh [w tym , i ] zapewnia szorstkie pojęcie równości przy porównywaniu funkcji. Nieco niepokojące jest wyrażenie takie jak , ale jego znaczenie można zawsze rozwiązać, wracając do definicji w kategoriach górnej i dolnej granicy. Być może najbardziej pouczające jest przeczytanie tutaj „=” jako „ jednej z funkcji, które są ”. Oczywiście, jest jedną z funkcji, które są .$O$$\Omega$$\Theta$$n^2 = O(n^3)$n 2 O ( n 3 )$n^2$$O(n^3)$

Ściśle mówiąc (jak zauważył komentarz Davida Richerby'ego ), daje ci szorstkie pojęcie równości, szorstkie pojęcie mniejszej lub równej, i i szorstkie pojęcie większej niż lub równej -do.$\Theta$$O$$\Omega$

Niemniej jednak zgadzam się z odpowiedzią Vincenzo : możesz po prostu interpretować jako zestaw funkcji, a symbol = jako ustawiony symbol członkostwa .$O(f(n))$$\in$

[1] Skiena, SS The Algorytm Design Manual (wydanie drugie). Springer (2008)

Zazwyczaj zdania takie jak można interpretować jako

Staje się to bardziej przydatne w kontekstach takich, jak wspomina David Richerby, gdzie piszemy co oznacza, że ​​„istnieje takie, że . ”$f(n) = n^3 + O(n^2)$$g(n) \in O(n^2)$$f(n) = n^2 + g(n)$

Uważam, że taka egzystencjalna interpretacja kwantyfikatora jest tak przydatna, że ​​kusi mnie pisanie takich rzeczy

które niektórzy uznają za bardziej rażące naruszenie stylu, ale jest to po prostu sposób na oszczędność miejsca „istnieje takie, że ”.$C$$f(n) \leq C n^3$

Wiele innych plakatów wyjaśniło, że Big-O można traktować jako oznaczający zbiór funkcji i że notacja wskazuje, że (jako funkcja ) znajduje się w zestaw oznaczony przez (ponownie biorąc pod uwagę jako parametr). W tekście angielskim możesz napisać „ jest w ”, aby uniknąć nieporozumień.$n^2 = O(n^3)$$n^2$$n$$O(n^3)$$n$$n^2$$O(n^3)$

Chociaż notacja może być myląca, może pomóc myśleć o i jako częściach tej samej notacji, to znaczy traktować jak jeden symbol. Różni się niewiele od tego, co robimy, gdy piszemy w języku programowania: dwa symbole obok siebie stają się jednym w naszych oczach.$O$$=$$= O$>=

Innym trudnym aspektem notacji jest to, że zmienna działająca jako parametr nie jest jednoznacznie identyfikowana ani związana , tak jak w deklaracji funkcji lub notacji lambda. Może to być szczególnie mylące, gdy w grę wchodzą dwie zmienne, jak w lub nawet bardziej w wyrażeniu takim jak ponieważ można sugerować, że jest stałą. Z drugiej strony niektóre algorytmy mają złożoność w zestawie Big-O, który technicznie zmienia się w zależności od dwóch zmiennych, podczas gdy w praktyce jeden z nich jest stały. Co więcej, może istnieć wiele rozsądnych sposobów pomiaru złożoności jednego algorytmu. Na przykład, jeśli dane wejściowe to liczba, algorytm może mieć wartość w wartości$O(mn)$$O(n^c)$$c$$O(n)$$n$liczby, ale w rozmiarze bitu liczby. (Chociaż w teorii złożoności per se, rozmiar bitu jest zwykle właściwym parametrem.)$O(2^b)$

Wszystko po to, by powiedzieć, że Big-O jest nieformalnym zapisem, prześladowanym przez niedokładność, i często trzeba użyć innego kontekstu, aby zrozumieć, co mówi autor.

Jak zawsze, najlepiej unikać zamieszania we własnym piśmie, i sugeruję unikanie i użycie zamiast niego lub angielskim „… jest w…”$= O$$\in O$

Aby podkreślić punkt, który został kilkakrotnie poruszony, pozwólcie, że cytuję z NG de Bruijn, Metody asymptotyczne w analizie :

Wspólną interpretację wszystkich tych wzorów można wyrazić w następujący sposób. Każde wyrażenie obejmujące symbol należy traktować jako klasę funkcji. Jeśli weźmie się pod uwagę zakres , wówczas oznacza klasę wszystkich funkcji w postaci , przy czym , . A oznacza, że ​​klasa jest zawarta w klasie$O$$0 < x < \infty$$O(1) + O(x^2)$$f(x) + g(x)$$f(x) = O(1)\,\,(0 < x < \infty)$$g(x) = O(x^2)\,\,(0 < x < \infty)$$x^{-1}O(1) = O(1) + O(x^{-2})$$x^{-1}O(1)$$O(1) + O(x^{-2})$. Czasami lewa strona relacji nie jest klasą, ale pojedynczą funkcją [...]. Zatem relacja oznacza, że ​​funkcja po lewej jest członkiem klasy po prawej.

Oczywiste jest, że znak jest naprawdę niewłaściwym znakiem dla takich relacji, ponieważ sugeruje symetrię i nie ma takiej symetrii. Na przykład jest poprawne, ale jest fałszywe. Po tym ostrzeżeniu używanie znaku nie zaszkodzi jednak i będziemy go utrzymywać wyłącznie z tego powodu, że jest to zwyczajowe.$=$$O(x) = O(x^2)\,\,(x \rightarrow \infty)$$O(x^2) = O(x)\,\,(x \rightarrow \infty)$$=$

Donald Knuth zwrócił również uwagę, że matematycy często używają znaku ponieważ używają słowa „jest” w języku angielskim. „Arystoteles jest mężczyzną, ale człowiek niekoniecznie jest Arystotelesem”.$=$

Powiedziawszy to, notacja Bendera i Orszaga (z Zaawansowanych metod matematycznych dla naukowców i inżynierów ) jest znacznie mniej myląca i warto ją rozważyć. W odniesieniu do pewnego limitu mówimy:

(wymawiane „ jest asymptotyczne do ”) oznacza$f$$g$

i:

(wymawiane „ jest nieznaczne w porównaniu do ”) oznacza$f$$g$

Ale przypuszczam, że zaletą notacji big-oh jest to, że stały czynnik jest arbitralny. (A dla notacji „o-oh” stałym czynnikiem jest cokolwiek z ciebie.)

Omówiłem to na stackoverflow ; chociaż być może najbardziej poprawna odpowiedź na OP została już podana powyżej (klasy równoważności, przekształcone poniżej jako nr 1), oto pełna odpowiedź:

1. zestawy : „ ” oznacza , tj. członkostwo w zestawie, np. „zbiór funkcji asymptotycznie ograniczony przez ”. Jest to standardowe matematyczne podejście do asymptotycznej notacji, o którym wiem. Ten zestaw ma częściową kolejność odpowiadającą podzbiorowi, np. (niektóre zestawy mogą być nieporównywalne; DAG; zobacz hierarchię wielomianów dla interesującego przykład).$f= O(\cdot)$$f \in O(\cdot)$$\{\frac{1}{2} x^2, (5 x^2-x+5), 2.5x,...\}$$x^2$$O(x^2) < O(x^3) = O(x^3 + x)$

   Uwaga. „ ” oznacza . Należy jednak zauważyć, że w przeciwieństwie do powyższego, jest to relacja równoważności (oczywiście naiwna relacja X jak w iff nie jest klasą równoważności, ponieważ nie implikuje ; banalna relacja równoważności „zarówno element ” jest być może zabawna w konceptualizacji, ale matematycznie nieciekawa, podczas gdy w wiele klas równoważności dzieli przestrzeń funkcji).$f= \Theta(\cdot)$$f \in \Theta(\cdot)$f X g$f \in O(g)$$f \in O(g)$$g \in f(g)$$O(g)$$\Theta$

2. wyrażenie wieloznaczne : Możesz przeformułować wstecz definicję : po pewnym promieniu odliczania w pobliżu źródła (tj. istnieje , taki że dla wszystkich ...), istnieje pasmo ograniczone stałymi wielokrotnościami które ograniczają (tj. ) ... a więc możemy to przeprogramować, aby po prostu zastąpić dowolne wyrażenie z wyrażeniem , to znaczy zamień go na samą granicę plus warunek błędu, na którym nam nie zależy (warunek błędu ograniczony przez dla$f \in \Theta(g)$$x_0$$x>x_0$$g$$f$$LOW*g(x) \le f(x) \le HIGH*g(x)$$O(g)$$k_1g(x)+err(x)$$0 \le err(x) \le k_2g(x)$$x>x_0$i potencjalnie nieograniczone dla ) ..... więc na przykład, jeśli powiedzieliśmy , moglibyśmy powiedzieć gdzie tym błędem jest . Nigdy jednak tego nie zapisalibyśmy ... bo to trochę głupie. Uważam jednak, że takie myślenie może być uzasadnione i zachowałoby pojęcie równości. (Przestrzegam tutaj właściwego traktowania znaków ujemnych, co może być ważne).$x\le x_0$$f = 2^{\Theta(x^2)}$$f(x)=2^{k_1x^2+err(x)}$$0 \le err(x) \le k_2x^2$

   za. Zmodyfikuj powyższe odpowiednio dla zamiast$O$$\Theta$

Bardziej dokładna odpowiedź byłaby taka, że ​​gdy mówimy, że funkcja f jest „dużym O funkcji g”. (Ie x ^ 2 + x to O (x ^ 2)) mówimy, że f (x) <C * g (x) dla pewnej wartości C i k gdzie x> k. Oznacza to, że g jest górną granicą dla zachowania f.

Przykład

x ^ 2 + 10x 4 to O (x ^ 2 + x), które samo w sobie jest O (x ^ 2)