«Информатиканың теориялық негіздері»
Функцияның ассимптотикалық анализі
жүктеу/скачать 0,6 Mb.
|
Функцияның ассимптотикалық анализіАлгоритмнің еңбеккөлемділігі функциясының мінез-құлқын талдау кезінде математикада қабылданған функцияның нақты коэффициенттерді бетперделеп, өсу жылдамдығын көрсететін асимптотикалық бейнелеуді жиі қолданады. Алгоритмнің еңбеккөлемділігін осылайша бағалау алгоритм күрделілігі деп аталады және бастапқы берілгендердің үлкен көлемдері үшін қай алгоритмді қолдану керектігін анықтауға мүмкіндік береді. В асимптотическом анализе приняты следующие обозначения: 1. (тетта) бағасы. Айталық, f(n) және g(n) – оң аргументті оң функциялар, n >= 1 (кірістегі объектілер саны және амалдар саны – оң сандар), сонда:
Әдетте мұнда 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) дегенді білдіреді. жүктеу/скачать 0,6 Mb. Достарыңызбен бөлісу:
|