Jakiej definicji asymptotycznej stopy wzrostu powinniśmy uczyć?

35

Kiedy postępujemy zgodnie ze standardowymi podręcznikami lub tradycją, większość z nas uczy następującej definicji notacji Big-Oh w pierwszych kilku wykładach klasy algorytmów: Być może podajemy nawet całą listę ze wszystkimi jej kwantyfikatorami:

f = O (g) iff (\exists c > 0) (\exists n_{0} \geq 0) (\forall n \geq n_{0}) (f (n) \leq c \cdot g (n)) .

$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).$

$f = o(g) \mbox{ iff } (\forall c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$
$f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$
$f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$ .

Ponieważ jednak definicje te nie są tak łatwe w obsłudze, jeśli chodzi o udowodnienie nawet prostych rzeczy, takich jak , większość z nas szybko wprowadza „trick of the limit”: $5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$

$f = o(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i wynosi $0$ ,
$f = O(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i nie jest $+\infty$ ,
$f = \Theta(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i nie jest ani $0$ ani $+\infty$ ,
$f = \Omega(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i nie jest $0$ ,
$f = \omega(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i wynosi $+\infty$ .

Moje pytanie brzmi:

Byłaby to wielka strata dla nauczania klasy algorytmów licencjackich podjęcia warunków granicznych jak w definicji $o$ , $O$ , $\Theta$ , $\Omega$ , a $\omega$ ? I tak wszyscy to wykorzystujemy i wydaje mi się całkiem jasne, że pominięcie definicji kwantyfikatora ułatwia życie wszystkim.

Byłbym zainteresowany, gdybyś napotkał jakiś przekonujący naturalny przypadek, w którym standardowe definicje są faktycznie wymagane, a jeśli nie, czy masz przekonujący argument, aby utrzymać standardowe definicje. $c,n_0$ $c,n_0$

ds.algorithms soft-question teaching

— slimton
źródło

1

Tag powinien naprawdę „uczyć”, ale nie mogłem znaleźć żadnego powiązanego tagu i nie mogę tworzyć nowych tagów.

— slimton

1

To w zasadzie absorbuje kwantyfikatory w definicji granic epsilon-delta. Moją jedyną obawą jest to, że wielu studentów CS nie przeprowadziło analizy, więc ich rozumienie granic jest głównie mechaniczne. Aby umożliwić im szybkie obliczanie, nie trzeba się zastanawiać.

— Per Vognsen

6

Zauważ, że twoje dwie definicje O () nie są równoważne (to samo zastrzeżenie dotyczy Θ () i Ω ()). Rozważ przypadek, w którym f (n) = 2n dla parzystej n oraz f (n) = 1 dla nieparzystej n. Czy f (n) = O (n)? Wolę używać limsup zamiast lim, aby w tym przypadku powiedzieć f (n) = Θ (n) (chociaż żadna z twoich definicji na to nie pozwala). Ale to może być moja osobista preferencja (a nawet niestandardowa praktyka) i nigdy nie uczyłem żadnej klasy.

— Tsuyoshi Ito

2

@Tsuyoshi: Myślałem, że sensem „sztuczki z limitem” jest to, że jest to wystarczający, ale nie konieczny warunek dla . (W przypadku jest to również konieczne.) Funkcja kontrprzykładowa nie ma limitu.

O ()

$O()$

o ()

$o()$

— András Salamon,

1

Czy nie należy zamieniać symbolu na w każdej definicji i właściwości? Uznałem, że użycie bardzo niepokojące jako student.

=

$=$

\in

$\in$

=

$=$

— Jeremy

13

Wolę uczyć oryginalnej definicji z kwantyfikatorami.

IMO, ludzie zazwyczaj mają problemy ze zrozumieniem formuł i definicji przy więcej niż dwóch naprzemiennych kwantyfikatorach bezpośrednio. Wprowadzenie nowych kwantyfikatorów może wyjaśnić, co oznacza definicja. Tutaj ostatnie dwa kwantyfikatory oznaczają po prostu „dla wszystkich wystarczająco dużych n”, wprowadzenie tego rodzaju kwantyfikacji może pomóc.

Obrazy, które rysuję dla wyjaśnienia tych pojęć, lepiej pasują do wersji kwantyfikatora.

Myślę, że uproszczenie limitu jest przydatne dla studentów inżynierii, którzy są zainteresowani tylko obliczeniem tempa wzrostu, ale nie będą tak przydatni dla studentów informatyki. W rzeczywistości korzystanie z tego uproszczenia może spowodować więcej szkody niż pożytku.

Pomysł ten jest podobny do sugestii, że używamy reguł obliczania pochodnych (wielomianów, potęgowania, ..., reguły łańcuchowej, ...) zamiast definicji epsilon-delta, co IMHO nie jest dobrym pomysłem.

— Kaveh
źródło

Pomocne jest także pojęcie dominacji: iff . Teraz iff jest st .

f (x) ≪ g (x)

$f(x) \ll g(x)$

\esits m \forall n > m f (n) < g (n)

$\esits m \forall n>m f(n) < g(n)$

f \in O (g)

$f \in O(g)$

c > 0

$c>0$

f (x) ≪ c g (x)

$f(x) \ll c g(x)$

— Kaveh

9

Edycja: Ważna wersja w wersji 3.

Ponieważ nigdy nie prowadziłem zajęć, nie sądzę, żebym mógł przekonująco twierdzić o tym, czego powinniśmy uczyć. Niemniej jednak oto, co o tym myślałem.

Istnieją naturalne przykłady, w których napisana „sztuczka z limitem”, jak jest napisana, nie może być zastosowana. Załóżmy na przykład, że zaimplementujesz „wektor o zmiennej długości” (jak wektor <T> w C ++) za pomocą tablicy o stałej długości z podwojeniem rozmiaru (to znaczy za każdym razem, gdy masz zamiar przekroczyć rozmiar tablicy, ponownie przydziel tablicę dwa razy większą niż teraz i skopiuj wszystkie elementy). Rozmiar S ( n ) tablicy, gdy przechowujemy n elementów w wektorze, jest najmniejszą potęgą o wartości 2 większej lub równej n . Chcemy powiedzieć, że S ( n ) = O ( n ), ale użycie „sztuczki z limitem”, jak jest zapisane jako definicja, nie pozwoli nam na to, ponieważ S ( n) / n oscyluje gęsto w przedziale [1,2). To samo dotyczy Ω () i Θ ().

Jako nieco odrębną kwestię, kiedy używamy tych notacji do opisania złożoności algorytmu, myślę, że twoja definicja Ω () jest czasami niewygodna (chociaż myślę, że ta definicja jest powszechna). Bardziej wygodne jest zdefiniowanie, że f ( n ) = Ω ( g ( n )) wtedy i tylko wtedy, gdy limsup f ( n ) / g ( n )> 0. Jest tak, ponieważ niektóre problemy są trywialne dla nieskończenie wielu wartości n ( np. idealny problem z obróbką na wykresie z nieparzystą liczbą n wierzchołków). To samo dotyczy Θ () i ω ().

Dlatego osobiście uważam, że następujące definicje są najwygodniejsze w opisie złożoności algorytmu: dla funkcji f , g : ℕ → ℝ _{> 0} ,

f ( n ) = o ( g ( n )) wtedy i tylko wtedy, gdy limsup f ( n ) / g ( n ) = 0. (Jest to równoważne z lim f ( n ) / g ( n ) = 0.)
f ( n ) = O ( g ( n )) wtedy i tylko wtedy, gdy limsup f ( n ) / g ( n ) <∞.
f ( n ) = Θ ( g ( n )) wtedy i tylko wtedy, gdy 0 <limsup f ( n ) / g ( n ) <∞.
f ( n ) = Ω ( g ( n )) wtedy i tylko wtedy, gdy limsup f ( n ) / g ( n )> 0. (Jest to równoważne z tym, że f ( n ) nie jest o ( g ( n )).)
f ( n ) = ω ( g ( n )) wtedy i tylko wtedy, gdy limsup f ( n ) / g ( n ) = ∞. (Jest to równoważne z tym, że f ( n ) nie jest O ( g ( n )).)

lub równoważnie

f ( n ) = o ( g ( n )) wtedy i tylko wtedy, gdy dla każdego c > 0, dla wystarczająco dużego n , f ( n ) ≤ c ⋅ g ( n ).
f ( n ) = O ( g ( n )) wtedy i tylko wtedy, gdy dla niektórych c > 0, dla wystarczająco dużego n , f ( n ) ≤ c ⋅ g ( n ).
f ( n ) = Θ ( g ( n )) wtedy i tylko wtedy, gdy f ( n ) = O ( g ( n )) if ( n ) = Ω ( g ( n )).
f ( n ) = Ω ( g ( n )) wtedy i tylko wtedy, gdy dla niektórych d > 0, dla nieskończenie wielu n , f ( n ) ≥ d ⋅ g ( n ).
f ( n ) = ω ( g ( n )) wtedy i tylko wtedy, gdy dla każdego d > 0, dla nieskończenie wielu n , f ( n ) ≥ d ⋅ g ( n ).

Ale nie wiem, czy jest to powszechna praktyka, czy nie. Nie wiem też, czy nadaje się do nauczania. Problem polega na tym, że czasami chcemy zamiast tego zdefiniować Ω () za pomocą liminf (jak w pierwszej definicji). Na przykład, kiedy mówimy „Prawdopodobieństwo błędu tego randomizowanego algorytmu wynosi 2 ^{Ω ( n )} ”, nie mamy na myśli, że prawdopodobieństwo błędu jest wykładniczo małe tylko dla nieskończenie wielu n !

— Tsuyoshi Ito
źródło

Używam również definicji limsup, ale dla studentów, którzy nie widzieli limsup (prawie wszystkie), muszę rozwinąć się w wyraźne kwantyfikatory.

— Jeffε

@JeffE: Zgadzam się, że większość uczniów nie widziała limsup, więc jeśli użyjemy definicji limsup, musimy zastosować kwantyfikatory w klasie.

— Tsuyoshi Ito,

2

Problem z wersjami kwantyfikatorów polega na tym, że są one trudne do zapamiętania i wizualizacji. Wolę ponieważ można go opisać jako „najwyższy punkt graniczny”. Możliwym wyjaśnieniem jest: „Jest jak , z tym wyjątkiem, że działa tylko wtedy, gdy sekwencja się zbiega. Jeśli sekwencja się nie zbiega, na przykład dlatego, że algorytm oscyluje między bardzo szybkim dla niektórych i wolnym dla innych , wówczas bierzemy najwyższy punkt graniczny. ”

l i m s u p

$limsup$

l i m

$lim$

l i m

$lim$

n

$n$

n

$n$

— Heinrich Apfelmus

Czy istnieją jakieś naturalne przykłady algorytmów, w których oscyluje czas działania?

— Heinrich Apfelmus

2

@ Heinrich: Wspomniałem już o czasie działania algorytmu, aby znaleźć idealne dopasowanie wykresu na n wierzchołkach, ale czy jest to naturalny przykład? Dodałem kolejny przykład, w którym czas działania nie oscyluje, ale oscyluje f (n) / g (n). Przykład mówi o złożoności przestrzeni, ale złożoność czasowa tego samego przykładu ma tę samą właściwość.

— Tsuyoshi Ito

8

Używanie limitów jest nieco mylące, ponieważ (1) jest to bardziej skomplikowane pojęcie (2), nie ujmuje ładnie f = O (g) (jak widzimy w powyższej dyskusji). Zwykle mówię o funkcjach od liczb naturalnych (ściśle dodatnich) do liczb naturalnych (co wystarcza na czasy wykonywania), pomijam te małe rzeczy, a następnie definicja jest zwięzła i odpowiednia dla studentów pierwszego roku:

Dfn: f = O (g) jeśli dla pewnego C dla wszystkich n mamy to f (n) <= C * g (n)

— Noam
źródło

1

Po pierwsze nie podobała mi się ta definicja, ponieważ określenie „all n” przesłania ważny fakt, że notacja O () dba tylko o zachowanie funkcji dla dużych n. Jednak bez względu na to, którą definicję wybieramy, sądzę, że powinniśmy wyjaśnić ten fakt wraz z definicją. Myśląc w ten sposób, sformułowanie tej prostej definicji wydaje się całkiem dobre.

— Tsuyoshi Ito

Chociaż to oddaje istotę, nie podoba mi się to, jeśli

f (n) = n

$f(n) = n$ dla wszystkich

,

dla wszystkich

do

, a

przeciwnym razie, to

ale ta definicja nie uwzględnia tego związku. Trzeba więc dodać trochę falowania o funkcjach, które są dobrze zachowane w pewnym sensie.

n

$n$

g (n) = 0

$g(n) = 0$

n

$n$

N_{0}

$N_0$

g (n) = f (n) + 1

$g(n) = f(n)+1$

f = O (g)

$f=O(g)$

— András Salamon,

2

Mówiąc o funkcjach, których zakresem jest liczba naturalna (nie licząc 0), nie należy wpadać w problemy z g (n) = 0.

— Noam

1

@Warren Victor Shoup w swojej książce na temat obliczeniowej teorii liczb używa notacji

zamiast

w analizie czasu pracy, co uważam za porządne.

l e n (a)

$len(a)$

\log a

$\log a$

— Srivatsan Narayanan

1

@Warren (ciąg dalszy) Oto, jak to wyjaśnia: „Wyrażając czasy działania algorytmów w kategoriach danych wejściowych

, zwykle wolimy pisać

niż

. Jednym z powodów jest estetyczny: pisanie

podkreśla fakt, że czas działania jest funkcją długości bitu

. Kolejny powód jest techniczny: w przypadku dużych

szacunków obejmujących funkcje w dowolnej dziedzinie, odpowiednie nierówności powinny utrzymywać się w całej dziedzinie, a dla z tego powodu korzystanie z funkcji, takich jak

, jest bardzo niewygodne

a

$a$

l e n (a)

$len(a)$

\log a

$\log a$

l e n (a)

$len(a)$

a

$a$

O

$O$

\log

$\log$ , które znikają lub są nieokreślone przy niektórych danych wejściowych. ”

— Srivatsan Narayanan

5

Kiedy wziąłem podstawowe kursy, dostaliśmy rzeczy jak określanie i inne rzeczy, jak twierdzenia. $\exists c,n_0 \dots$

Myślę, że pierwszy z nich jest bardziej naturalny dla wielu ludzi, którzy myślą raczej dyskretnie niż nieprzerwanie, to znaczy większość informatyków (z mojego doświadczenia). Pasuje również sposób, w jaki zwykle mówić o tych rzeczach lepiej: „Nie jest wielomianem funkcją stopnia 3, który stanowi górne ograniczenie dla tej dokładnością do czynnika stałego”. $f$

Edycja : Możesz zbliżyć się do tego sposobu mówienia, używając tej definicji: (Zauważ, że łączy tę definicję z tą, która jest zwykle podawana) $f \in \mathcal{O}(g) :\Leftrightarrow \exists c,d > 0 \forall n \geq 0 : f(n) \leq c\cdot g(n) + d$ $d=f(n_0)$

Ograniczenia są bardzo przydatne do obliczania klas złożoności, czyli za pomocą pióra i papieru.

W każdym razie uważam, że bardzo przydatne jest, aby uczniowie dowiedzieli się, że istnieje wiele (miejmy nadzieję) równoważnych definicji. Powinny być w stanie to zrozumieć i wybrać różnice w przypadku niejednoznacznych definicji.

— Raphael
źródło

4

Studiując te koncepcje zaledwie kilka lat temu, nie były najtrudniejsze do zrozumienia dla mojej klasy (w przeciwieństwie do takich pojęć, jak indukcja czy kontrpozytywność). Limity i limity są tylko bardziej „intuicyjne” dla tych, którzy znają rachunek różniczkowy moim zdaniem. Ale studenci z takim uziemieniem matematycznym i tak będą mieli ustawione podstawy teoretyczne, aby mogli przetwarzać dyskretne kwalifikatory.

Co ważniejsze, pamiętaj, że ostatecznie twoi uczniowie będą (miejmy nadzieję) czytać inne podręczniki teorii cs, a może nawet pewnego dnia artykuły badawcze. W związku z tym lepiej jest, aby czuli się komfortowo ze standardową notacją w terenie, nawet jeśli początkowo nie była idealna. Nie ma nic złego w podawaniu im alternatywnych definicji, gdy tylko przyswoją sobie standardowe.

— Amir
źródło

3

Ciekawe spojrzenie na ten temat można znaleźć w ładnie napisanym liście Dona Knutha „Rachunek za pomocą notacji O” . Opowiada się za odwrotnym poglądem, że rachunku różniczkowego należy uczyć za pomocą notacji „A”, „O” i „o”.

$x$ $A$ $y$ $x = A(y)$ $|x| \leq y$ $100$ $A(200)$

— Srivatsan Narayanan
źródło

1

Definicje Tsuyoshi Ito nie wyglądają całkiem dobrze. W przypadku małych omega i dużych omega definicje powinny używać liminf, a nie limsup. Definicja big-theta wymaga zarówno dolnej granicy limf, jak i górnej granicy limsup.
Jedna z definicji f (n) = O (g (n)) jest taka, że istnieje inna funkcja f '(n)> = f (n) taka, że lim f' (n) / g (n) <nieskończoność.
Dlaczego początkujący mogą publikować odpowiedzi, ale nie mogą komentować?

— Warren Schudy
źródło

1

Jeśli chodzi o punkt 1, mam na myśli limsup we wszystkich przypadkach, a przyczynę wyjaśniono w drugim akapicie mojej odpowiedzi.

— Tsuyoshi Ito

niestety jest to mechanizm blokujący spam.

— Suresh Venkat

Również w swoich odpowiedziach możesz użyć lateksu.

— Suresh Venkat

1

Najpierw próbuję rozwinąć u studentów intuicję , zanim pokażę równania.

„Sortuj według sortowania vs Sortowanie wstawiane” jest dobrym punktem wyjścia.

f = O (g) iff (\exists c > 0) (\exists n_{0} \geq 0) (\forall n \geq n_{0}) (f (n) \leq c \cdot g (n)) .

$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).$

lim_{n \to \infty}

$\lim_{n \rightarrow \infty}$

Innym aspektem jest to, że w dużej mierze zależy to od konkretnego programu badań. IMHO, w zależności od poprzednich tematów, będzie bardziej odpowiednia z jednej z definicji - podczas gdy IMHO nadal dobrze jest pokazać obie i zaakceptować oba rodzaje rozwiązań.

— Grzegorz Wierzowiecki
źródło