Notacja asymptotyczna O II-opracowanie

Notacja asymptotyczna O II Podana definicja oznacza, ˙ze f ma zło˙zono´s´c rz˛edu g , je´sli istnieje taka liczba dodatnia c 1, ˙ze f jest niewi˛eksza od c 1 g dla dostatecznie du˙zych n , czyli dla dla wszystkich n wi˛ekszych od pewnej ustalonej liczby n 0. Zwia˛zek mie˛dzy f i g oznacza, z˙e albo g jest kresem górnym dla f , albo ˙ze od pewnego miejsca f ro´snie nie szybciej ni˙z g . Przykład: f ( n ) = n 2 + 100 n + log 10 n + 1000 Dla małych warto´sci n ostatni wyraz jest najwi˛ekszy. Kiedy n = 10, drugi i ostatni wyraz sa˛ tego samego rze˛du, zas´ pozostałe maja˛ do wyniku niewielki wkład. Kiedy n osia˛ga wartos´c´ 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˙zych warto´sci n , z uwagi na kwadratowy post˛ep pierwszego wyrazu ( n 2), warto´s´c funkcji f zale˙zy głównie od niego, a pozostałe wyrazy na dłuz˙sza˛mete˛ traca˛ na znaczeniu. ... zobacz całą notatkę