Otwórz menu główne

Asymptotyczne tempo wzrostu – miara określająca zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.

Do opisu asymptotycznego tempa wzrostu stosuje się notację dużego (omikron; U+039F, kod HTML: Ο, Math: \Omicron) oraz jej modyfikacje, m.in. notacja (omega), (theta).

Notacja dużego została zaproponowana po raz pierwszy w roku 1894 przez niemieckiego matematyka Paula Bachmanna[1]. W późniejszych latach spopularyzował ją w swoich pracach Edmund Landau, niemiecki matematyk, stąd czasem nazywana jest notacją Landaua.

Spis treści

Definicje analityczneEdytuj

Niech będą dane funkcje   oraz   których dziedziną jest zbiór liczb naturalnych, natomiast przeciwdziedziną zbiór liczb rzeczywistych dodatnich.

Notacja „duże O”Edytuj

Mówimy, że   jest co najwyżej rzędu   gdy istnieją takie stałe   oraz   że:

 

Zapis:  

Określenia „złożoność co najwyżej  ” i „złożoność  są matematycznie równoważne.

Wersja notacji dla zachowania się funkcji w pobliżu punktu  

  jeżeli istnieje takie   i takie   że dla każdego   o tej własności, że   zachodzi nierówność:

 

Należy zauważyć, że nie precyzuje się tu dziedziny funkcji   i   – zależy ona od kontekstu w jakim występują obie funkcje.

Notacja „małe o”Edytuj

Mówimy, że   jest niższego rzędu niż   gdy dla każdej stałej   istnieje stała   że:

 

Zapis:  

Notacja „Ω”Edytuj

Mówimy, że   jest co najmniej rzędu   gdy istnieją takie stałe   oraz   że:

 

Zapis:  

Notacja „ω”Edytuj

Mówimy, że   jest wyższego rzędu niż   gdy dla każdej stałej   istnieje stała   że:

 

Zapis:  

Notacja „Θ”Edytuj

Mówimy, że   jest dokładnie rzędu   gdy istnieją takie stałe   oraz   i   że:

 

Zapis:  

Można powiedzieć, że   gdy   jest jednocześnie rzędu   i  

WłaściwościEdytuj

Notacja dużego   pozwala wykonywać działania na funkcjach, na przykład:

  • jeśli   i   to również  
  • przy założeniach jak poprzednio,  

Wygoda notacji dużego   widoczna jest w następującej sytuacji: jeżeli   to można napisać zarówno   jak i   czy wreszcie   zależnie od wymaganej dokładności oszacowań.

Napis   należy rozumieć jako  

Zależności algebraiczne Edytuj

Notacja Warunek wystarczający
   
   
   
   
   

Trychotomia może nie wystąpić w żadnym przypadku (lecz może w przypadku niektórych funkcji i argumentów). Przechodniość, zwrotność, symetria, symetria transpozycyjna są zawsze prawdziwe tylko w przypadku wymienionych zależności funkcji asymptotycznie dodatnich[2].

Przechodniość:

 
 
 
 
 

Zwrotność:

 
 
 

Symetria:

 

Symetria transpozycyjna:

 
 

TwierdzenieEdytuj

Dla dowolnych dwóch funkcji   i   zachodzi zależność:

 [2]

PrzykładyEdytuj

  • Jeżeli   oraz   to   oraz   ale również  
  • Niech   Korzystając ze wzorów sumacyjnych:   a zatem  
  • Jeżeli potrzebne jest dokładniejsze oszacowanie   to na podstawie tego samego wzoru sumacyjnego można napisać  
  • Analogicznie można napisać, że  

Standardowe oszacowaniaEdytuj

W zastosowaniach szczególnie często notacja dużego   pojawia się w następujących sytuacjach:

  •   – funkcja   jest ograniczona
  •   – funkcja   jest ograniczona przez funkcję logarytmiczną
  •   – funkcja   jest ograniczona przez funkcję liniową
  •  
  •   – funkcja   jest ograniczona przez funkcję potęgową lub wielomian
  •   – funkcja   jest ograniczona przez funkcję wykładniczą
  •   – funkcja   jest ograniczona przez silnię

Rząd złożoności obliczeniowejEdytuj

W zależności od asymptotycznego tempa wzrostu, funkcje dzieli się na rzędy złożoności obliczeniowej. Najczęściej wyróżnia się:

  stała (stała liczba operacji niezależnie od liczby danych wejściowych)
  logarytmiczna
  liniowa
  liniowo-logarytmiczna (lub quasi-liniowa)
  kwadratowa
  wielomianowa
  wykładnicza

ZastosowanieEdytuj

Najczęstszym zastosowaniem asymptotycznego tempa wzrostu jest szacowanie złożoności problemów obliczeniowych, w szczególności algorytmów. Oszacowanie rzędów złożoności obliczeniowej funkcji pozwala na porównywanie ilości zasobów (np. czasu, pamięci), jakich wymagają do rozwiązania problemu opisanego określoną ilością danych wejściowych. W dużym uproszczeniu można powiedzieć, że im niższy rząd złożoności obliczeniowej algorytmu, tym będzie on wydajniejszy przy coraz większym rozmiarze problemu (np. ilości danych do algorytmu).

W praktyce na efektywność algorytmu wpływa duża ilość innych czynników, w tym szczegóły realizacji. Ponadto dla małych danych wejściowych asymptotyczne tempo wzrostu może nie oddawać zachowania funkcji – np. gdy   (funkcja liniowa  ) i   (funkcja logarytmiczna  ), zachodzi oszacowanie   (  asymptotycznie rośnie szybciej niż  )[potrzebny przypis], ale dla   wartość funkcji   jest mniejsza niż funkcji  

Istnieje również wiele sytuacji kiedy algorytm ma lepszą złożoność obliczeniową niż inne, ale nie stosuje się go, ponieważ jego przewaga w faktycznej implementacji jest widoczna dopiero dla gigantycznych (i kompletnie niepraktycznych) wielkości wejścia, lub ma inne wady (na przykład niestabilność numeryczną – porównaj Algorytm Strassena). Innym powodem może być na przykład fakt, że algorytm ma lepszą złożoność czasową, ale gorszą złożoność pamięciową i vice-versa (tzw. space-time tradeoff).

Zobacz teżEdytuj

PrzypisyEdytuj

  1. Ronald L Graham, Donald Ervin Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2002, s. 489. ISBN 83-01-13906-4.
  2. a b Thomas H. Cormen i inni, Wprowadzenie do algorytmów, Krzysztof Diks i inni, Wydanie VII (I w PWN), Warszawa: PWN, 2015.