Алгоритмдердің тиімділігі

Алгоритм қандай да бір машинада командалардың жинағы түрінде орындалады. Бір есепті орындауға арналған екі немесе бірнеше алгоритмдердің орындалу жылдамдығын салыстыру үшін қолданылатын критерий (өлшем) жүйелік тиімділік деп аталады. Бір компьютерде бірдей деректер жинағымен бұл алгоритмдерді орындату арқылы олардың орындалуына кеткен салыстырмалы уақытты анықтауға болады.Ол үшін ішкі жүйелік сағат қолданылады.

Ішкі жүйелік сағатты қолданып уақытты бағалау бұл бір ғана есептің орындалуына арналған алгоритмдердің әрқайсысының жүйелік тиімділігінің өлшемі болады.

Кейбір алгоритмдердің орындалуында жадқа қойылған шектеулер проблема тудырады. Орындалу барысында ұзақ уақыт сақтау үшін бастапқы көлемді қысу қажет болады. Қандай да бір алгоритм пайдаланатын ішкі жадтың салыстырмалы санының өлшемі — бұл кеңістіктің тиімділігі (space efficiency). Бұл критерий алгоритмді қандай типті компьютер орындай алатынын және алгоритмнің толық жүйелік тиімділігін көрсетеді. Жаңа компьютерлік жүйелердің жадтарының көлемінің ұлғаюна байланысты бұл критерий маңызды болмай қалды.

Үшінші тиімділік критерийі — бұл есептеу тиімділігі (computational efficiency), ол алгоритмнің ішкі құрылымын қарастырады, оның жасалуын және алгоритмде қолданылатын итерациялар мен меншіктеу операторларын салыстыратын тесттердің санын да талдайды. Бұл өлшем типі нақты компьютерге тәуелсіз және бұл критерий алгоритмнің есептелу күрделілігін n-ге, яғни коллекциядағы деректер элементеріне қатысты өлшейді.

Іздеу алгоритмдерінің күрделілігін бағалау -Big-0 нотациясы

Әдетте күрделі алгоритмнің ен жаман және ең жақсы жағдайлары үшін әртүрлі есептеу тиімділігі болады, сондықтан әр жағдай үшін есептеу тиімділігін өлшеу үшін, яғни алгоритмнің орындалу уақытының өлшемін анықтау үшін Big-0 нотациясын есептейміз.

Big-0 нотациясы. Алгоритмнің есептеу тиімділігі өңделетін деректердің санымен, яғни алгоритмдегі басты операциялардың санымен анықталады. Бұл операциялар деректің типіне, санына, реттелуіне тәуелді болады. Көп жағдайда сұрыптау алгоритмдерінде (тізімдер мен бұтақтарда) алгоритм тиімділігін өлшемі ретінде салыстыру қолданылады. Ол массив элементтерінің санына тәуелді.

Мысалы массивтегі минимал элементті табу — бұл қарапайым алгоритм, оның негізгі операциясы элементтерді салыстыру. n элементі бар массив үшін алгоритм n-1 салыстыруды қажет етеді, оның тиімділігінің өлшемі n-ге пропорционал. Басқа алгоритмдер күрделі.. Алмастырып салыстыру алгоритмінде жалпы салыстыру саны:

f(n) = (n — 1) + (n — 2) +... + 3 + 2 + 1 = n(n — 1)/2 арифметикалық қатармен анықталады. f(n) функциясы салыстырумен ассоциацияланады. Бұл алгоритмнің салыстыру саны n² болады.

Big-O нотациясын есептеу тиімділігінің өлшемін беру үшін қолданады. Алгоритмнің есептеу күрделілігінің (оны f(n) функциясы немесе салыстырулар саны дейді) реті O(g(n)) -ге тең болады, мысалы алмастырып сұрыптаудың есептеу күрделілігі О(n²) тең. Сызықты алгоритмнің күрделілігі тізімнің размеріне пропорционал болады, оның O(g(n)) - реті О(n) тең.

О(n2) реті бар алгоритмдер квадраттық деп аталады.

Іздеу алгоритмдерінің күрделілігі.

Big-O-бағалау алгоритмнің орындалу уақытының өлшемін (run­time) береді. Әдетте алгоритмнің жақсы және нашар жағдайлар үшін есептеу тиімділіктері әртүрлі, сондықтан әр нақты жағдай үшін Big-О мәні есептеледі.

Егер алгоритм реті — 0(1) болса, оның реті коллекциядағы элементтер санына тәуелсіз болады. Бұл алгоритм тұрақты уақыт бірлігі ішінде орындалады, мысалы егер массив соңын көрсететін индекс сақталса, массив элементіне мән меншіктеу реті 0(1) болады.

Алгоритм О(п) сызықты (linear). Оның күрделілігі тізім размеріне пропорционал.

Реті log₂n болатын алгоритмдер лога­рифмдік (logarithmic) деп аталады. Мұндай күрделілік тізімдерді бірнеше рет ішкі тізімдерге 1/2, 1/4, 1/8 етіп бөлгенде туындайды. Мысалы бинарлық бұтақтарда іздеу алгоритмдерінің күрделілігі орташа және нашар жағдайлар үшін O(log₂n) болады.

Реті О(п²) болатын алгоритмдерквадраттық (quad­ratic) деп аталады. Шағын n үшін ғана практикада қолданылады. п екіге артқан сайын алгоритмнің орындалу уақыты 4-ке артады.

Реті О( n³ ) болатын алгоритмдер өте баяу орындалады, кубтық (cubic) уақытты қажет етеді. п екіге артқан сайын алгоритмнің орындалу уақыты 8 есе артады. Оның мысалына графтарға қолданылатын реті О(п³) болатынУоршел алго­ритмі жатады.

Күрделілігі О(2^п) тең алго­ритмде экспоненциальды күрделілік (ex­ponential complexity) болады. Өте баяу орындалатындықтан өте аз п үшін қолданылады.

Төмендегі кестеде аталған алгоритмдердің ретінің бағалауы берілген, аз мәнді п үшін кубтық, экспоненциальдық алгоритмдерді қолдану тиімсіз.

Тізімдер мен бұтақтар сияқты коллекциялардың жалпы кластарының деректерін өңдеу үшін алгоритмнің тиімділігінің өлшемі ретінде салыстыру қолданылады.

Алгоритмнің қиындығын талдау.

Алгоритмнің қиындығын талдаудың мақсаты берілген есепті шешуге арналған тиімді алгоритмді табу. Алгоритмнің тиімділігінің критерийі ретінде алгоритмнің қиындығы таңдалады. Алгоритмнің қиындығы деп осы алгоритм көмегімен есепті шешуге арналған элементар операциялардың санын айтады. Қиындық функциясы деп алгоритмнің кірістік деректерін элементар операциялардың санымен байланыстыратын қатынасты айтады.