Ќазаќ мемлекеттік ќыздар педагогика институты
жүктеу/скачать 1,32 Mb.
|
- Бұл бет үшін навигация:
- Дәріс №15. Алгоритмдерді талдау
| Әдебиеттер
Негізгі әдебиеттер: 6 [179-114], 3 [60-75] Қосымша әдебиеттер: 2[135-141] – б, 3[89-93] – б. Бақылау сұрақтары Файл деген не? Файлдың массивтен айырмашылығы? Логикалық файл деген не? Физикалық файл деген не? Файлдарға қандай ұғымдар тән? Файл компоненті деген не? Файлдың неше түрі бар? Дәріс №15. Алгоритмдерді талдау Құрамында циклы жоқ әрекеттер Рекурентті тізбектерді өңдеу Тиімді, жылдам жұмыс істейтін алгоритмдер құрудың практикалық есептер шығаруда бірінші дәрежелі болмаса да, үлкен мәні бар. Бірнеше алгоритмдердің ішінен жылдам жұмыс істейтін алгоритмді таңдау үшін олардың жұмыс уақытын салыстырып үйрену қажет. Дегенмен, жұмыс уақытын дәл есептеу мүмкін емес. Бұл уақыт алдымен программа орындалатын компьютердің шынайы сипаттамасына тәуелді болуы мүмкін. Әдетте алгоритмнің орындалуы уақыты тек жуықтап қана есептеледі. Сонымен бірге жұмыс уақытына арналған формула мәндері тек тәжірибелік жолмен анықталатын қандай да бір сандық тұрақтылардан тұрады. Мұндай бағалаудың өзі көбінесе ең тиімді бір алгоритмді ғана таңдауға мүмкіндік береді. Басқа жағдайларда жұмыс уақытын бағалаудың көмегімен баяу жұмыс істейтін алгоритмдерді шығарып тастауға болады, ал қалғандарынан программаның шынайы жұмыс уақытын өлшеудің көмегімен таңдауға болады. Енді жоғарыда айтылғандарды мысалмен түсіндірейік. Мысалы, қандай да бір n саннан құрылған тізбекті өңдеу қажет болсын. Мұндағы n өзгеріп отыратын болсын. Осы есепті шығаруға екі программа берілсін, олардың жұмыс уақыты жуықтап С1n C2n2, мұндағы С1 және С2 –- тұрақтылар, олар n-ге тәуелсіз. N үлкен болған жағдайда бірінші программа жылдам жұмыс істейді, ал n аз шама болғанда программа баяу жұмыс істейді. Бұл С1 > С2 екенін көрсетеді. С1 С2 -ден 5 есе үлкен болсын. С1 =5С2 . С1 n =5С2 n мен C2n2-ты салыстыра отырып, n>5 болғандағы программаның жұмыс уақытының баяу, ал n<5 болғанда екінші программаның жылдам жұмыс істейтінін байқауға болады. Мұндағы n =5 бағалау уақытының шектік мәні де жуықтап тағайындалады. Бұдан екі тұжырым жасауға болады. Біріншіден, «тұрақтыға дейінгі дәлдікпен» жуықтап бағалаудың өзі алгоритмдерді салыстыруда пайдалы болып табылады. Екініден, есеп шығарудың бір алгоритмі өте жылдам деп айтуға болмайды. Қандай да бір алғашқы мәліметтер жиынтығы үшін кейбір алгоритм екіншісінен тиімді болуы мүмкін. Енді программаның жұмыс уақытын анықтайтын алғашқы мәліметтердің мұндай сипаттамасын таңдау мәселесіне тоқталайық. Мұндай сипаттама есептің өлшемі деп аталады. Әртүрлі есептерді шығару уақытына алғашқы мәліметтердің әртүрлі қасиеті әсер етеді. Мысалы, минимумды іздеу немесе әрбір сан бір бүтін сан ретінде қарастырылатын берілген сандарды іріктеу типті есептер үшін алғашқы сандар мөлшері есептер мөлшері болып табылады. Қарапайым көбейткіштерге жіктеу есебі үшін санның шамасы мөлшері болып есептеледі. Есеептің мөлшерін таңдау қандай да бір шығару алгоритмі туралы жалпы ұғымға негізделеді. 2n дәрежесін есептеу алгоритмін қарастырайық. Дәрежелеудің санның бірінен соң бірі көбейтілетінін ескере отырып, өлшем ретінде n дәреже көрсеткішті аламыз. Өлшемді сипаттаудың тағы бір тәсілі нәтижедегі цифр сан ыболып табылады. 2n дәрежесіндегі цифр саны n-ге пропорционал, сондықтан екі өлшем де эквивалентті. Жұмыс уақытын бағалау мезетіндегі маңызды кезең – орындалу барысында барлық жұмыс уақытының негізгі бөлігін алатын программа бөлігін іздеу болып табылады. Көптеген программалар үшін экспериментті түрде дәлелденген факт: жұмыс уақытының негізгі бөлігі программа мәтінінің шағын бөлігін орындауға кетеді. Программаның мұндай бөлігі цикл деп аталады. Көпшілік жағдайда жұмыс уақытын жуықтап бағалау талап етіледі, сондықтан программаның қалған бөлігінің орындалу уақытын ескермеуге болады, тек ішкі циклдың орындалуын қарастыруға болады. Егер программа бірінің ішіне бірі орналасқан бірнеше программадан тұратын болса, онда ішкі циклды табу жеңіл. Әрине, алдымен, бәрінен бұрын барлық циклға қатысты программа бөлігі орындалады, ал бұл қалған барлық циклдардың ішіндегі және ішінде басқа цикл болмайтын циклдар болып табылады. Бұл бақылау программаның жиі орындалатын бөлігі үшін «ішкі цикл» деген атауды дәлелдей түседі. Егер ішкі циклды қамтымайтын бірнеше цикл болса, олардың әрқайсысының қайталану санын есептеуге болады. Егер бір циклдың қайталану саны басқаларымен салыстырғанда айтарлықтай үлкен болатын болса, онда басқа циклдардың жұмыс уақытын ескермеуге болады; кері жағдайда соңғы формулада жұмыс уақыты үшін бірнеше циклдардың орындалу уақытын ескеруге тура келеді. Параметрлі қайталану командасындағы қайталану саны For операторы үшін төмендегі формуламен есептеледі: Циклдың басы For i:=A to B Егер B>=A-1 болса, онда қайталану саны B - A +1 –ге тең; Егер BFor i:=A downto B циклі үшін А мен В-ның орындарын ауыстыру қажет. Егер программада цикл бір рет орындалатын болса, онда бұл формула ақиқат болып есептеледі. Енді бұл циклдың басқа циклдың ішінде бірнеше рет қайталанып орындалған жағдайын қарастырайық. Цикл ішіндегі қайталану санын шартты түрде цикл денесінің орындалу санының саны деп атайық. Барлық циклдың орындалу санын цикл тақырыбының орындалу саны деп атайық. Сөйтіп, цикл тақырыбының бір рет орындалуы цикл денесінің қанша рет орындалатынын көрсетеді. Бірінші формула оның тақырыбы цикл денесінің бір рет орындалуындағы цикл денесінің орындалу санын береді. Егер қарастырылып отырған цикл басқа циклдың ішінде орналасқан болса, онда онда оның тақырыбы бірнеше рет орындалады да, цикл денесінің орындалуының жалпы санын табу үшін осы цикл тақырыбының барлық орындалуы барысындағы (1) формуламен алынған сандарды қосу қажет. Бұл формуланы қолданудың қарапайым мысалы ретінде төмендегі программа фрагментін талдайық: For j:=1 to n do Begin (*1-цикл *) For k:=1 to M do (* 2-цикл денесі*) For l:=n downto j do (* 3-цикл денесі*) End; Екінші және үшінші цикл денелерінде ішкі цикл жоқ, ал, M және N – қандай да бір үлкен тұрақтылар. 2 және 3-циклдардың қайталану санын бағалайық. Екеуі де бірінші циклдың ішінде орналасқан, олардың қай талану саны (1) формула бойынша оңай есептеледі; ол N-1+1=N-ге тең. Бұл қайталанулардың әрқайсысында 2-цикл денесі М-1+1=М рет орындалады. М саны тұрақты болғандықтан 2-цикл денесінің жалпы орындалу саны N2= N∙М тең. 3-цикл денесі 1-цикл денесінің әрбір орындалуында N-J+1 рет орындалады. Бұл санның М санынан айырмашылығы 1-циклдың орындалуы барысында өзгеріп отырады; сондықтан екі санды тек көбейте салуға болмайды:3-цикл денесінің барлық орындалу санын қосу қажет. Бұдан 1-циклдың орындалуында J айнымалысы 1-ден N-ге дейінгі барлық мәндерді қабылдайды (міне дәл осы 1-цикл тақырыбында жазылған. Сөйтіп, 3-цикл денесінің жалпы орындалу саны: Бұл арифметикалық прогрессияны ңқосындысы; ол (N+1) ∙ N/2 тең. Уақыт жуықтап есептелінетіндіктен N-мен салыстыруға жүгібей-ақ, формуланы жеңілдетуге болады: N3 жуықтап N2/2 тең. N2 мен N3-ті салыстыра отырып, бұл сандардың біреуі екіншісінен әлдеқайда артық деп айта алмаймыз. Керісінше, қандай да бір N мен М үшін олар бір ретте болады. Мысалы, егер М= N, онда N2 шамамен N3-тен 2 есе үлкен болады. Сондықтан жұмыс уақыты үшін формулаға екі циклға да жауап беретін екі қосылғыш қосуға тура келеді. Цикл денелерінің бір реттік орындалу уақытын есептей отырып, тұрақтыларды Т2 және Т3 арқылы белгілеп, жалпы жұмыс уақытын есептеу үшін төмендегідей жуықтатылған формуланы аламыз: Т =М∙N∙Т2+(N2/2) ∙Т3. Егер цикл денелерінің орындалу уақытын тұрақты деп есептемейтін болса (мысалы, онда шартты оператор немесе процедураны шақыру болса), онда алдымен денелердің орындалу уақытын талдап, одан кейін оларды қосу қажет. Жұмыс уақыты жөнінде бұдан да дәл ақпаратты әртүрлі алғашқы мәліметтер бойынша программа программа жұмысының шынайы уақытын өлшеу нәтижесі бойынша алуға болады. Бұл эксперименттердің көмегімен формулаға кіретін белгісіз тұрақтыларды (біздің жағдайда Т2 және Т3) бағалауға болады. Енді нақты программа жұмысын талдауға көшейік, 2N дәрежесін есептеуді қарастырайық. Программа жұмысы циклды қамтитын екі ірі бөліктен тұрады. Ол 2N дәрежесін есептеу және баспаға шығару. Программаның жұмыс уақытын бағалауда әдетте, баспаға шығару уақытын емес, тек есептеуге кететін уақыт ескеріледі. Бұл көптеген есепті шығару алгоритмі үшін басу уақыты өте аз болғандықтан ескерілмейді. Сонымен қатар, өте үлкен N үшін есептеу уақыты аз болғандықтан ескермеуге де болады. Басып шығаруды және циклған кірмейтіндерді шығарып тастағаннан кейін төмендегідей программма аламыз: For K:=1 To N Do Begin (*1-цикл*) For I:=еңҮлкенҰзындық DownTo XБасы Do Begin (*2-цикл *) жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу:
|