Matematyka dyskretna 1/Wykład 9: Asymptotyka

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Widzieliśmy już, że wskazanie postaci zwartej dla ciągu zadanego równaniem rekurencyjnym jest często zadaniem niełatwym. Do tej pory nie jest znana zwarta postać wielu równań. Na szczęście często jesteśmy w sytuacji, w której zadowoli nas przybliżenie odpowiedzi. Wróćmy do rozważanej wielokrotnie sumy kolejnych kwadratów . Fakt, że jest to wielomian -go stopnia zmiennej , to już wartościowa informacja, często zupełnie wystarczająca. Spotkaliśmy się już nie raz z oszacowaniami poprzez zwykłe nierówności. To podejście często wymaga użycia narzędzi z analizy matematycznej, w szczególności znajdowania ekstremum funkcji.

Przykład

Silnię liczby naturalnej można trywialnie oszacować przez . Przyjrzyjmy się delikatniejszemu oszacowaniu wskazującemu także dolne ograniczenie na .

Najpierw zauważmy, że



Potraktujmy jako wielomian drugiego stopnia zmiennej . Łatwo zauważyć, że dla przybiera on najmniejszą wartość w punkcie , a największą w punkcie . Zatem dla mamy i dalej



czyli



Nierówności w oszacowaniach bywają niepotrzebnie krępujące. Zaś wyniki w ten sposób otrzymane, często skupiają naszą uwagę na zbędnych i czasem nieinteresujących detalach. Często bowiem wystarczają nam przybliżone, asymptotyczne oszacowania ciągów lub ogólniej funkcji. Opisują one zachowanie funkcji wraz ze wzrostem argumentu. Podczas przekształceń rachunkowych celowo ograniczamy naszą wiedzę o funkcji, dzięki czemu łatwiej jest rachować i otrzymać zadowalającą postać przybliżającą.

W oszacowaniach asymptotycznych posługujemy się ogólnie przyjętymi symbolami opisującymi asymptotyczne zachowanie jednej funkcji wobec drugiej. Najpowszechniej używany jest symbol przydatny w analizie górnej granicy asymptotycznej. Po raz pierwszy tego symbolu użył niemiecki teorio-liczbowiec Paul Bachmann w 1894. Prace Edmunda Landau'a (także niemieckiego teorio-liczbowca) spopularyzowały tę notację, stąd czasami jest nazywany symbolem Landau'a. Notację asymptotyczną wprowadzimy jedynie dla funkcji zdefiniowanych na zbiorze (lub jego podzbiorach postaci ) o wartościach w .

Notacja asymptotyczna

SW_7.1.swf

Funkcja asymptotycznie niewiększa od funkcji to taka funkcja , dla której istnieją i , że dla wszystkich .
Będziemy też często mówić, że zachodzi dla prawie wszystkich liczb naturalnych .
Zbiór funkcji asymptotycznie niewiększych niż oznaczamy przez .

Ponieważ jest zbiorem funkcji, poprawnie powinniśmy zapisywać , gdy spełnia warunek podany w definicji. Jednak przyjęło się zapisywać . Jest to pewne nadużycie symbolu równości . Jednak tradycja, a jak się niebawem okaże, również i wygoda użycia, są wystarczającym usprawiedliwieniem dla tego nadużycia. W związku z tym napis czytamy " jest -duże od ".

Przykład

  • , to zbiór funkcji ograniczonych.

Istotnie warunek zachodzący dla prawie wszystkich łatwo jest, poprzez zamianę stałej na inną , sprowadzić do warunku zachodzącego już dla wszystkich , jako że skończenie wiele wartości dla początkowych daje się ograniczyć przez stałą.

    • każda funkcja stała jest np. jest , bo dla dowolnego ,
    • , bo dla dowolnego ,
    • , bo dla dowolnego ,
    • , bo dla , zatem dla .
  • to zbiór funkcji ograniczonych przez funkcję liniową:
    • wszystkie funkcje są też ,
    • , bo dla ,
    • , bo dla dowolnego .
    • ,
    • ,
    • (funkcja ta jest także i ).
    • , bo , a zatem dla dowolnego .

Więcej przykładów i ogólniejszych obserwacji poznamy po prezentacji pozostałych pojęć i symboli notacji asymptotycznej.

SW_7.2.swf

Funkcja asymptotycznie niemniejsza od funkcji to taka funkcja , dla której istnieją i , że dla wszystkich .
Zbiór funkcji asymptotycznie niemniejszych niż oznaczamy przez .

Funkcja asymptotycznie podobna do funkcji to taka funkcja , dla której istnieją i , że dla wszystkich .
Zbiór funkcji asymptotycznie podobnych do oznaczamy przez . A zatem .

Pozostałe dwa symbole: są rzadziej stosowane w informatyce. Wyznaczają one funkcje asymptotycznie, ściśle mniejsze [większe] od podanej funkcji.

Funkcja asymptotycznie mniejsza od funkcji to taka funkcja , że dla każdego istnieje , przy którym dla wszystkich .
Zbiór funkcji asymptotycznie mniejszych niż oznaczamy przez . A zatem wtedy i tylko wtedy, gdy .

Funkcja asymptotycznie większa od funkcji to taka funkcja , że dla każdego istnieje , przy którym dla wszystkich .
Zbiór funkcji asymptotycznie większych niż oznaczamy przez . A zatem wtedy i tylko wtedy, gdy .

Oto kilka prostych faktów wiążących kolejne symbole asymptotyczne. Pozostawiamy je bez dowodu.

Obserwacja 9.1

Dla funkcji mamy:

  • jeśli , , to ,
  • jeśli , , to ,
  • jeśli , , to ,
  • jeśli , , to ,
  • wtedy i tylko wtedy, gdy ,
  • wtedy i tylko wtedy, gdy ,
  • wtedy i tylko wtedy, gdy .

Symbole asymptotyczne mogą pojawić się w złożonych wyrażeniach arytmetycznych. Dla przykładu wspomnijmy jeszcze raz sumę kolejnych kwadratów: . Możemy teraz napisać , ale także , co formalnie oznacza . Co więcej okazuje się, że symbol może pełnić nie tylko rolę , ale czasami także rolę . Na przykład wyrażenie



ma po obu stronach"równości" zbiory funkcji, przy czym po lewej stronie są to wszystkie funkcje postaci dla . W tej sytuacji znak powinien być formalnie rozumiany jako inkluzja .

Nadużywając znaku "równości" musimy jednak uważać i pamiętać, że w konwencji asymptotycznej taki nadużyty znak nie jest relacją symetryczną. Rzeczywiście, , gdyż np. funkcja , ale . Jednak pożytki płynące z takiego "przeciążenia" znaku równości sprawiedliwiają te nadużycia. W następnej Obserwacji w taki właśnie sposób sformułujemy (bez oczywistego dowodu) kilka własności notacji . Z nich mozna łatwo otrzymać analogiczne własności dla i .

Obserwacja 9.2

Dla funkcji mamy:

  • ,
  • wtedy i tylko wtedy, gdy ,
  • wtedy i tylko wtedy, gdy ,
  • wtedy i tylko wtedy, gdy ,
  • jeśli i , to ,
  • jeśli i , to .

Przykład

Pokażemy, że wielomiany -tego stopnia są .

Zauważmy najpierw, że jeśli to , czyli jeśli to . Rozważmy zatem dowolny wielomian -tego stopnia , gdzie . Wtedy



co dowodzi, że .

Dla dowodu , niech . Wtedy



dla . Mamy zatem



co dowodzi .

Przykład

Często pojawiają się logarytmy o różnych podstawach. Najczęściej są to . Z asymptotycznego punktu widzenia wszystkie te funkcje są podobne tzn. np. i , lub ogólniej:



Rzeczywiście, jest to po prostu wzór na zamianę podstaw logarytmu,



gdzie ta sama stała jest dobra do dolnego i górnego ograniczenia.

Przykład

Dla wielomianów rząd ich wielkości wyznaczony jest przez stopień:


wtedy i tylko wtedy, gdy
.


Ustala to hierarchię rzędów funkcji:



Również dla "stopni" będącymi dowolnymi liczbami dodatnimi mamy:


wtedy i tylko wtedy, gdy


Na przykład:

  • ,
  • .

Przykład

Mamy . Istotnie łatwo dowieść indukcyjnie, że .

Podobnie . Wiemy już, że każda funkcja liniowa jest w , istnieje więc stała taka, że od pewnego miejsca .
Pokażemy, że wtedy też . Indukcyjnie



Analogicznie, wiedząc już, że każda funkcja kwadratowa jest w , czyli że dla pewnej stałej od pewnego miejsca mamy { }, możemy pokazać indukcyjnie, że . Istotnie



Ogólnie, dla dowolnego stopnia mamy , o ile tylko .

Przykład

Oczywiście , więc .
Ale . Gdyby bowiem to



podczas gdy funkcja wykładnicza rośnie do nieskończoności. Nie może zatem być ograniczona przez żadną stałą .
Ogólnie dla , mamy wtedy i tylko wtedy, gdy .

Przykład

Mamy oraz .
Istotnie , bo każdy czynnik (poza pierwszym) w jest równy co najmniej . Pokazuje to, że .

Podobnie , bo każdy czynnik w jest nie większy niż .

Jako ćwiczenie pozostawiamy dowód następnej obserwacji.

Obserwacja 9.3

Oto ciąg funkcji, z których każda jest od następnej, ale nie od poprzedniej:



i dalej



W istocie, gdy występuje w tym ciagu wczesniej niż , to

  • ,
  • .

Przykład

Nie każde dwie funkcje są porównywalne asymptotycznie. Na przykład dla funkcji



i mamy i .

Twierdzenie o rekursji uniwersalnej

Podstawowym zastosowaniem notacji asymptotycznej w informatyce jest szacowanie długości działania programów, w szczególności procedur rekurencyjnych, których złożoność łatwo opisać równaniem rekurencyjnym. Niech będzie funkcją opisującą złożoność czasową pewnego programu, czyli zwracającą liczbę wykonywanych operacji dla danych wielkości . Zazwyczaj nie jesteśmy zainteresowani dokładną liczbą wykonywanych operacji, a jedynie dobrym oszacowaniem z góry i czasem z dołu. Dlatego zamiast szukać postaci zwartej rozwiązania rekurencyjnego, co na ogół jest zadaniem beznadziejnym, dopuszczamy użycie notacji asymptotycznej i szukamy pewnej "dobrze znanej" funkcji takiej, że . Znając wiemy w jaki sposób rośnie długość działania programu wraz z wzrostem wielkości danych.

Równania, o których mówimy często są postaci , czyli aby rozwiązać problem dla danych wielkości , rozwiązujemy podproblemów wielkości i składamy z nich rozwiązanie całości w dodatkowym czasie . Twierdzenie o rekurencji uniwersalnej wskazuje funkcję asymptotycznie podobną do w bardzo wielu przypadkach.

Twierdzenie 9.4 [o rekurencji uniwersalnej]

Dla funkcji zadanej przez



zachodzi:

  • jeśli dla pewnego , to ,
  • jeśli , to ,
  • jeśli dla pewnego oraz dla pewnego i prawie wszystkich , to .

Zanim podamy dowód Twierdzenia 9.4, poczynimy kilka uwag i prześledzimy kilka przykładów.

W praktyce na ogół pomijamy opis początkowych wartości funkcji domyślnie przyjmując, że są one . Nie będziemy też używać podłóg w wyrażeniach typu , traktując występujące tu dzielenie jako całkowito-liczbowe. Twierdzenie o rekurencji uniwersalnej jest silnym i praktycznym narzędziem. Jednak trzeba podkreślić, że nie szacuje ono rozwiązań wszystkich równań typu . Taka niemożność oszacowania może mieć miejsce z jednego z trzech powodów, przy czym drugi z nich jest istotny i zdarza się w praktyce:

  • W każdym z trzech przypadków opisanym w twierdzeniu, porównujemy funkcje i . Może się zdarzyć (jak widzieliśmy w jednym z przykładów), iż i są asymptotycznie nieporównywalne i wobec tego nie będzie można zastosować żadnego z tych trzech przypadków. Na szczęście w praktyce takie funkcje raczej zdarzają się niezmiernie rzadko.
  • Po drugie, w przypadku pierwszym (i trzecim), tak naprawdę, porównujemy z funkcją istotnie mniejszą (wiekszą) od , tzn. z funkcją dla pewnego . Ten warunek już może przeszkadzać w praktyce. Dla przykładu , ale dla dowolnego . Pełny przykład takiego równania przedstawimy poniżej.
  • Po trzecie, w ostatnim warunku dla dla dowolnego wymagamy dodatkowo, żeby dla pewnego i dla wszystkich dla pewnego . Znów, na szczęście, w większości spotykanych sytuacji ten warunek "regularności" jest spełniony. Jednak zawsze trzeba go sprawdzić.

Przykład

Dla funkcji zadanej przez:



dostajemy kolejno:

Podobnie dla funkcji



mamy:

Niech teraz



Wtedy

Z kolei dla funkcji spełniającej



dostajemy

  • , , ,
  • ,
  • ale dla dowolnego , ,
  • i ... nie można zaaplikować Twierdzenia 9.4.

Po tych uwagach i przykładach podamy dowód Twierdzenia o rekurencji uniwersalnej.

Dowód

Rozumowanie nasze przeprowadzimy tylko w przypadku, gdy liczba występująca w rekurencyjnym równaniu zadającym funkcję jest potęgą liczby naturalnej, czyli dla liczb postaci . Rozszerzenie tego rozumowania na cały zbiór jest dość techniczne i wymaga szacowania podłóg. Ponadto, symboli asymptotycznych będziemy używać tylko dla . To nieformalne nadużycie nie ogranicza poprawności rozumowania -- wymaga wszakże rozszerzenia notacji asymptotycznej na funkcje postaci .

Rozwijając rekurencyjną formułę dla otrzymujemy:



Ponieważ możemy kontynuować:



Dalsze szacowanie rozbijamy na przypadki zgodnie z warunkami na zachowanie funkcji wobec :

  • ,


Ponieważ i są stałymi, ostatni składnik redukuje się do . Zatem


  • ,
  • dla pewnego i prawie wszystkich

oraz .

Z założeń tego przypadku mamy . Zatem



End of proof.gif

Metoda przybliżeń

W pewnych sytuacjach łatwiejsze do uzyskania, ale słabsze oszacowanie zastosowane w odpowiedni sposób może prowadzić do lepszego końcowego szacowania zachowania asymptotycznego. Poznamy tę metodę w kilku kolejnych przykładach.

Przykład

Dla ciągu zadanego przez



najpierw dowodzimy indukcyjnie, że , czyli . Podstawiając uzyskane oszacowanie do równania rekurencyjnego otrzymujemy:



Operację tę możemy powtórzyć uzyskując jeszcze lepsze oszacowanie



Wykorzystaliśmy tu fakt, iż szereg jest zbieżny. Zauważmy też, że następne powtórzenie podobnej procedury szacującej już nam nic nie da.



Przykład

Niech ciąg spełnia



Z monotoniczności funkcji dostajemy, że . Podstawiając to oszacowanie za drugie wystąpienie w równaniu otrzymujemy:



czyli . Podstawiając powtórnie dostajemy:



czyli . Uzyskaliśmy zatem, że .

Na zakończenie tego wykładu poznamy jeszcze jeden symbol asymptotyczny. Jest on podobny do lecz znacznie precyzyjniejszy.

Funkcje asymptotycznie równe to takie funkcje i , że



Fakt, że funkcje i są asymptotycznie równe zapisujemy jako .

Jednym z najbardziej znanych przybliżeń asymptotycznych jest tzw. Wzór Stirlinga przybliżający zachowanie silni.

Twierdzenie 9.5 [wzór Stirlinga]



Wzór ten został odkryty przez Abrahama de Moivre w postaci



dla pewnej stałej . Wkładem Jamesa Stirlinga było pokazanie, że stałą tą jest . Dowód tego oszacowania wykracza poza metody tego kursu. W oszacowaniach przez nierówności przydatna jest następująca wersja wzoru Stirlinga:



Innym ważnym przybliżeniem asymptotycznym jest wzór na liczbę podziałów liczby naturalnej na sumy dodatnich liczb naturalnych, tzn. asymptotyczne przybliżenie funkcji .

Twierdzenie 9.6



Podamy też asymptotyczne przybliżenie na liczbę liczb pierwszych nie większych niż .

Twierdzenie 9.7

Jeśli oznacza liczbę liczb pierwszych w zbiorze , to