Алгоритмнің еңбеккөлемділігі функциясының мінез-құлқын талдау кезінде математикада қабылданған функцияның нақты коэффициенттерді бетперделеп, өсу жылдамдығын көрсететін асимптотикалық бейнелеуді жиі қолданады.
Алгоритмнің еңбеккөлемділігін осылайша бағалау алгоритм күрделілігі деп аталады және бастапқы берілгендердің үлкен көлемдері үшін қай алгоритмді қолдану керектігін анықтауға мүмкіндік береді. В асимптотическом анализе приняты следующие обозначения:
1. (тетта) бағасы.
Айталық, f(n) және g(n) – оң аргументті оң функциялар, n >= 1 (кірістегі объектілер саны және амалдар саны – оң сандар), сонда:
|
f(n) = (g(n)), егер төмендегідей с1, с2, n0 оң сандар бар болса: с1 * g(n) =< f(n) =< c2 * g(n),
мндағы n > n0
|
Әдетте мұнда g(n) функциясы f(n)функциясының асимптотикалық нақты бағасы деп айтылады, себебі, f(n)функциясы анықтамасы бойынша g(n) функциясынан тұрақты көбейткіш дәлдігімен айырмашылығы жоқ. Ескерту: f(n) = (g(n)) теңдігінен g(n) = (f(n)) екені шығады.
Мысалдар:
1) f(n)=4 +nlnN+174 – f(n)= ( );
2) f(n)= (1) – жазбасы f(n) немесе нольге тең емес константаға тең, немесе f(n) тұрақтысымен шектелген: f(n) = 7+1/n = (1) дегенді білдіреді.
Достарыңызбен бөлісу: |
