Jakiej definicji asymptotycznej stopy wzrostu powinniśmy uczyć?

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:

1. $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))$
2. $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))$
3. $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))$
4. $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))$
5. $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})$

1. $f = o(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i wynosi $0$ ,
2. $f = O(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i nie jest $+\infty$ ,
3. $f = \Theta(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i nie jest ani $0$ ani $+\infty$ ,
4. $f = \Omega(g)$ jeśli $\lim_{n \rightarrow \infty} f(n)/g(n)$ istnieje i nie jest $0$ ,
5. $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 $c,n_0$$c,n_0$

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.

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 !

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)

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 d = f ( n 0 ) łą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.

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.

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)$

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.

2. 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ść.

3. Dlaczego początkujący mogą publikować odpowiedzi, ale nie mogą komentować?

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

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

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