Notacja asymptotyczna OI-opracowanie

Notacja asymptotyczna O I Najpowszechniej uz˙ywana notacja opisuja˛ca złoz˙onos´c´ asymptotyczna˛ ( P. Bachmann, 1894 r. ) Niech f ( n ) ; g ( n ) ; n 2 N be˛da˛ funkcjami ze zbioru liczb naturalnych w zbiór liczb rzeczywistych. Powiemy, ˙ze funkcja f ( n ) jest rz˛edu najwy˙zej g ( n ) , co oznaczamy O ( g ( n )) , jez˙eli istnieja˛ stałe dodatnie c 1 2 R ; n 0 2 N takie, z˙e: 8 n n 0 ; f ( n ) 6 c 1 _ g ( n ) na przykład: f ( n ) = 3 _ n 3 + n 2 Ü n + 113 f ( n ) = const f ( n ) = O ( n 3 ) f ( n ) = O ( 1 ) ... zobacz całą notatkę