Әдістемелік құрал
АЛГОРИТМДЕР АНАЛИЗІ ЖӘНЕ БАҒДАРЛАМАЛАРДЫ
жүктеу/скачать 1,24 Mb. Pdf көрінісі
|
Алгоритм және оның мүмкіндіктері
| АЛГОРИТМДЕР АНАЛИЗІ ЖӘНЕ БАҒДАРЛАМАЛАРДЫ
ОРЫНДАУ АНАЛИЗІ Бір есепті шешуге арналған әртүрлі алгоритмдерді салыстыру үшін бағдарламаның орындалу уақытын жуық мөлшерде анықтау үшін алгоритмдердің математикалық анализі қолданылады. Қолданбалы есептерді шешу процесінде есеп шығарудың неғұрлым жақын алгоритмін таңдау керек болады. Мұнда алгоритм келесі талаптарды қанағаттандыруы керек: 1. Түсінуге жеңіл, бағдарламалық кодқа және орындауға, аударуға жеңіл болуға тиіс. 2. Компьютер ресурстарын тиімді пайдалану және орындалу жылдамдығы неғұрлым тез болуы керек. Бағдарламаның орындалу уақытына келесі факторлар әсер етеді: 1. Алғашқы ақпаратты бағдарламаға енгізу. 2. Орындалып жатқан бағдарламаның компилияцияланған кодының сапасы. 3. Бағдарламаның орындалуында пайдаланылып жатқан машиналық инструкциялар. 4. Сәйкес бағдарлама алгоритмінің уақытша күрделілігі. Алгоритмнің Уақыт бойынша күрделілігі дегеніміз – жоспарланған 63 нәтижеге жету үшін алгоритмге орындау қажет болатын қадамдармен өлшенетін алгоритмнің орындалу уақыты. Бұл терминнің синонимі ретінде, көбінесе алгоритмнің орындау уақыты сөзі пайдаланылады. Бағдарламаның орындалу уақыты алғашқы мәліметтердің мөлшеріне тәуелді. Мысалға, массивтегі ең кіші элементті табу бұл мәліметтер элементтерін салыстыруға негізгі операция немесе амал. N элементтерін массиві үшін алгоритмге N-1 салыстыру қажет болады және оның орындалу уақыты Т-ге пропорционал. Алгоритмдердің уақыт бойынша күрделілігін 0 символика деген қолданылады. Мысалы, егер қандай да бір бағдарламаның орындалу уақыты Т(n) О(n 2 ) ретке ие болса, бұл дегеніміз қандай да бір С әлде n 0 константалар болып, n 0 - дан үлкен немесе тең болатын n константалар үшін Т(n)<=cn 2 теңсіздігі орындалады. Яғни, орындалу уақыты ең аз дәрежеде өсетін бағдарламаларды таңдап алуы керек. Бұл дегеніміз, неғұрлым өсу дәрежесі аз болса, компьютердің шығарып отырған есептің өлшемі соғұрлым көп болады деген сөз. Бағдарламаның орындалу уақытын теориялық түрде табу күрделі математикалық есеп, оның шешілу үшін бірнеше базалық принциптерді білу керек. Алдымен 3 маңызды ережелерді қарастырамыз: 1. Тұрақты көбейткіштер уақыт бойынша күрделі реттік анықтау үшін маңызды емес, яғни О(k*f)=0. 2. Көбейткіштер ережесі: екі функцияның уақыт бойнша күрделі реттің көбейткіштері олардың күрделіліктің О(f*g)=O(f)*O(g). 3. Қосындылар ережесі: функцияның уақыт бойынша күрдел реттің қосындылары қосылғыштардың ең үлкенінің ретіне тең болады. О(n 5 +n 2 +n)=O(n 5 ). жүктеу/скачать 1,24 Mb. Достарыңызбен бөлісу:
|