69028

Notacja asymptotyczna Oli

Podana definicja oznacza, ze f ma zło zono s'crz,edug, je śli istnieje taka liczba dodatnia cl, ze f jest mewi,eksza od clg dla dostatecznie du zychn, czyli dla dla wszystkich n większych od pewnej ustalonej liczby nO.

Zwia,zekmie, dzyf i g oznacza, z e albo g jest kresem górnym dla f, albo ze od pewnego miejsca f ro śnie me szybciej ni zg.

Przykład: f (n) = n2+100n+logl0n+1000

Dla małych warto scin ostatni wyraz jest największy. Kiedy n = 10, drugi i ostatni wyraz są tego samego rze, du, zas' pozostałe maja, do wyniku niewielki wkład. Kiedy n osiągawartosc' 100 , pierwszy i drugi wyraz maja, taki sam wkład w wynik, kiedy n przekracza 100, drugi wyraz tez traci na znaczeniu. Wobec tego dla dużych warto scin, z uwagi na kwadratowy post,ep pierwszego wyrazu (n2), warto s c funkcji f żale zy głównie od niego, a pozostałe wyrazy na dłuż sza, mete, tracą na znaczeniu.