Әдістемелік құрал
Бағдарламалар анализінің ережелері
жүктеу/скачать 1,24 Mb. Pdf көрінісі
|
Алгоритм және оның мүмкіндіктері
| Бағдарламалар анализінің ережелері:
1. Меншіктеу, оқу және жазу операторларының орындалу уақыты О(1) ретке ие болады. 2. Операторлар тізбегінің орындалу уақыты қосындылар ережесі бойынша анықталады. 3. Шартты оператордың орындалу уақыты шартты түрде орындалып отырған оператордың орындалу уақытынан тұрады. Логикалық өрнекті есептеу уақыты – жалпы О(1) ретке ие болады. Барлық шарт конструкциясының уақыты логикалық өрнекті есептеу уақытынан және логикалық өрнек, ақиқаты және жалған мәндерді қабылдауда жүзеге асатын операторларды орындауға қажет ең көп уақыттан тұрады. 4. Циклдарды орындау уақыты – цикл денесі оператордың орындалу уақытынан және циклды тоқтату шартын есептеудің уақытынан тұратын барлық цикл итерацияларының уақытын қосқанға тең болады. 64 Сұрыптауға жататын элементтер саны кіретін мәліметтер көлемге өлшем бірлігі болып ткабылады. Мұндағы соңғы үш оператор О(1) орындалу ретіне ие болады. Қосындылар дәрежесіне сәйкес бұл операторлар топтары О(мах(1,1,1))=О(1). Егер операторы үшін логикалық өрнекті тексеру О(1) уақыт ретіне тең болады. Соңғы 5 оператор тобының, яғни ішкі циклдің орындалу ретін қарастырамыз, бұл операторлар үшін әрбір итеракциядағы орындалу уақыты О(1)- ге ие болады. Цикл n-1 рет орындалады. Сондықтан, көбейткіш ережесі бойынша циклдің барлық орындалу уақыты: О((n-1)*1)=O(n*1). Сыртқы циклді қарастырамыз: сыртқы цикл n-1 рет орындалады, сондықтан бағдарламаның жалпы қосынды орындалу уақыты − = − = − = − 1 1 2 2 / ) 2 ( 2 / ) 1 ( ) ( n i n n n n i n формуламен анықталады және О(n 2 ) ретке ие болады. Жалпы О функциясының мәні берілгендер құрылымы алгоритмдер үшін полиномдық, логорифмдік және экспоненциалдық функциялар ішінен таңдап алынады. жүктеу/скачать 1,24 Mb. Достарыңызбен бөлісу:
|