У рачунарској науци, алгоритамска ефикасност је свосјтво алгоритма које је повезано са количином рачунарских ресурса које алгоритам користи. Алгоритам мора бити анализиран да би се одредило његово коришћење ресурса. Алгоритамска ефикасност може бити замишљена и као аналогна са инжињерском продуктивношћу током понављаног или континуалног процеса.

За максималну ефикасност желимо да минимизирамо коришћење ресурса. Међутим, различити ресурси (нпр. време, простор) не могу бити поређени директно, тако да то који је од два алгоритма ефикаснији често зависи од тога која мера за ефикасност је најважније, нпр. потреба за великом брзином, минималним коришћењем меморије или нека друга мера. Обратите пажњу да овај чланак није о оптимизацији, која је дискутована у програмској оптимизацији, оптимизацији компајлера, оптимизацији петље итд. Термин "оптимизација" је сама по себи збуњујућа, јер све то генерално може да се замисли као "побољшање". Позадина Важност ефикасности је у прошлости нагласила Ејда Кинг Лавлејс 1843. применом механичког аналитичког мотора Чарлса Бебиџа:"У скоро сваком рачунању могућа је велика разноликост уређења наследства процеса, и различита разматрања морају да утичу на селекцију међу њима за сврхе рачунајућег мотора. Један важни објекат је бирање уређења које тежи да смањи минимално време потребно за завршавање рачунице.Green, Christopher, Classics in the History of Psychology, retrieved 19 May 2013Стари електронски рачунари су врло ограничени и од стране брзине операција и количине доступне меморије. У неким случајевима је увиђено да постоји простор-време размена, при чему задатак може бити решен коришћењем брзог алгоритма који заузима прилично пуно меморије, или коришћењем спорог алгоритма који користи врло мало радне меморије. Инжињерска размена је онда била да се користи најбржи алгоритам који би стао у доступну меморију.

Модерни рачунари су много бржи од раних рачунара, и имају много већу количину доступне меморије (гигабајте уместо килобајта). Ипак, Доналд Кнут је нагласио да је ефикасност и даље важна за разматрање: "У утврђеним инжињерским дисциплинама 12% побољшања, лако добијених, никада није сматрано маргиналним и ја верујем да исти начин гледања треба да буде примењен у софтверском инжињерству"

Преглед Алгоритам се сматра ефикасним ако његова потрошња ресурса (или рачунска вредност) на или испод неког прихватљивог нивоа. Грубо речено, "прихватљивих" значи: радиће разумно много времена на доступном рачунару. Од 1950-их компјутери су доживели драматично повећање доступне рачунарске моћи и доступне меморије, тако тренутни прихватљиви нивои би били неприхватљиви чак и пре 10 година.

Произвођачи компјутера често доносе нове моделе, често са бољим перформансама. Цене софтвера могу бити врло високе, тако да је у неким случајевима најједноставнији и најјефтинији начин да се добиу боље перформансе да се купи бржи рачунар, уз обезбеђење да је компатибилан са постојећим рачунаром.

Постоји много начина мерења колико алгоритам користи ресурса: два најчешћа мерења су брзина и коришћење меморије; друга мерења би могла да укључују брзину преноса, привремено коришћење диска, дугорочно коришћење диска, потрошња енергије, цена поседовања, време реаговања на спољашње стимулације, итд. Многе од ових мерења зависе од величине уноса у алгоритам (нпр. количина података који треба да се процесуирају); могу такође да зависе од начина на који су подаци распоређени (нпр. неки алгоритми за сортирање се лоше показују на подацима који су већ сортирани, или који су сортирани у обрнутом редоследу).

У пракси, постоје други фактори који утичу на ефикасност алгоритма, као што су захтеви за прецизношћу и/или поузданошћу. Доле објашњен, начин на који је алгоритам имплементиран може имати велики ефекат на ефикасност, кроз много аспеката ово је повезано са проблемима оптимизације.

Теоретске анализе У теоретској анализи алгоритама, нормална пракса је да се процени њихова комплексност у асимптотском смислу, нпр. коришћење нотације велико О да се репрезентује комплексност алгоритма као функције са улазом величине н. Ово је генерално довољно прецизно када је н велико, али може бити спутавајуће за мале вредности н (нпр. бабл сорт може бити бржи од квиксорта када само неколико ствари треба да се сортира).

Неки примери великог О укључују: Notation Name Examples константно Проверавање да ли је број прав или прост; коришћењем табеле константне величине; коришћењем одговарајуће хеш функције за тражење. логаритамско Тражење у сортираном низу са бинарним претраживањем или балансирано претраживачко дрво као и све операције у биномиалној гомили. линеарноТражење у несортираној листи или неправилном дрвету (најгори случај) или у несортираном низу; Сабирање два н-битна цела броја са рипл керијем. логлинеарно или квазилинеарно Извођење брзе Фуријеве трансформације;хипсорт, квиксорт (најбољи и просечни случај), или мрџсорт. квадратноМножење два н-тоцифрена броја једноставним алгоритмом; бабл сорт (најгори случај или наивна имплементација), шелсорт, квиксорт (најгори случај), селекшн сорт или инсершн сорт. експоненцијалноТражење егзактног решења проблема путујућег трговца коришћењем динамичког програмирања; одређивање да ли су две логичке изјаве еквивалентне коришћењем брут форс претраживања.

Тестирање: мерење перформанси За нове верзије или да се омогући поређење компетитивних система, тестирање се понекад користи, који асистирају са мерењем алгоритамских релативних перформанси. Ако се на пример произведе нови алгоритам за сортирање може бити упоређен са својим прецима да би се осигурало да је ефикасан као и раније са познатим подацима- узимајући у обзир сва функционална побољшања. Тестирања могу да користе муштерије када упоређују различите производе алтернативних добављача да би проценили који производ ће најбоље да одговара њиховим потребама у смислу функционалности и перформанси. На пример у главном делу светског власништва продуката за сортирање у независним софтверским компанијама као што је Синксорт се такмиче са продуктима које добављају велики добављачи као што је IBM за брзину.

Нека тестирања обезбеђују прилике за произвођење анализе која упоређује релативну брзину различитих састављених и интерпретираних језика на пример и The Computer Language Benchmarks Game упоређује перформансе имплементација типичних програмерских проблема у неколико програмских јзика.

(Чак и стварање "уради сам" тестирања да би се добила макар нека захвалност релативних перформанси различитих програмских језика, коришћењем различитих критеријума специфицираних од стране корисника, је лако да се произведе "окупљање групе девет перформансних језика" од Кристофера Ковела демонстрира на примеру)

Проблеми имплементације Проблеми импементације могу да имају ефекат на ефикасност, као што је избор програмског језика, или начина на који је алгоритам кодиран, или избор компајлера за одређени језик, или компилација поменутих опција, или чак који се оперативни систем користи. У неким случајевима језик који се имплементира од стране интерпретатора може бити много спорији од језика имплементираног од стране компајлера.

Постоје други фактори који могу да утичу на временске или просторне проблеме, али који могу бити ван контроле програмера; они укључују усклађивање података, грануларност података, скупљаче ђубрета, паралелизам на нивоу инструкција, позиви подрутина.Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO".

Неки процесори имају способност векторског процесуирања, које дозвољава да једна инструкција оперише над више операнада; то може и не мора да буде лако програмерима или компајлерима да користе. Алгоритми дизајнирани за секвенцијално процесуирање можда треба да буду потпуно редизајнирани да би се искористило паралелно процесуирање.

Још један проблем који може да настане са компатибилним процесорима је да они могу да имплементирају инструкцију на различите начине, тако да инструкције које су релативно брзе на неким моделима, на другим моделима могу да буду релативно споре; ово може загорчати живот оптимизирајућем компајлеру.

Мере коришћења ресурса Мере се обично представљају као функције са величином лаза н.

Две најчешће мере су: Време: колико је алгоритму потребно да се заврши. Простор: колико радне меморије (типично рам) је потребно алгоритму. Ово има два аспекта: количина меморије потребна за код, и количина меморије потребне за податке над којима код оперише. За компјутере чија је снага снадбдевена батеријом (нпр. лаптопови), или врло дуге/велике калкулације (нпр. суперкомпјутери), друге мере од интереса су: Директна потрошња снаге: снага потребна да би се директно оперисало рачунаром. Индиректна потрошња снаге: снага потребна за хлађење, осветљење, итд. У неким случајевима друге мање честе мере могу да буду такође релевантне: Величина преноса: проток може да буде ограничавајући фактор. Компресија података може да се искористи да се смањи количина података за слање. Приказивање слике (нпр. лого Гугла) може да резултује слањем десетина хиљада бајтова (48 хиљада у овом случају) у поређењу са слањем шест бајтова за текст"Google". Спољашњи простор: простор потребан на диску или на другојм спољашњем уређају; ово може да се користи за привремено складиштење док се алгоритам извршава, или може бити дугорочна меморија потребна за касније референцирање. Време одзива: ово је посебно важно за апликацију у реалном времену када комјутерски систем треба брзо да реагује на спољашње догађаје. Укупна цена поседовања: посебно ако је компјутер намењен за један посебан алгоритам.

Време

Теорија Анализирање алгоритма, типично коришћењем анализе временске комплексности да се добије просек времена извршавања као функција за величину унетих података. Резултат је обично представљен нотацијом велико О. Ово је корисно за упоређивање алгоритама, посебно када се велика количина података процесуира. Детаљније процене су потребне за поређење алгоритама када је количина података мала (иако у овој ситуацији време не може да буде неки проблем у сваком случају). Алгоритми који укључују паралелно процесуирање могу да буду тежи за анализирање.

Пракса Коришћење тестирања да се измери корисност алгоритма. Многи програмски језици имају доступну функцију која даје потрошњу времена процесора. За алгоритме који дуго трају протекло време може бити значајно. Резултати би генерално требало да буду упросечени кроз неколико тестова.

Овај тип тестирања може бити веома осетљив на хардверску конфигурацију и могућности програмера или проблема да се догађају истовремено на мулти процесуираном и мулти програмерској околини.

Ова врста теста такође зависи много од селекције одређеног програмског језика, компајлера, и компајлерских опција, тако алгоритми који се пореде морају бити имплементирани под истим околностима.

Простор Ова секција се бави коришћењем главне меморије (често РАМ) док се алгоритми дешавају. Као и временска анализа изнад, анализа алгоритама, типично користећи анализу временске комплексности да се процени меморија потребна за функцију за унесене податке. Резултат је често представљен нотацијом велико О.

Постоји чак четири аспекта коришћења меморије који треба да се размотре: Количина меморије потребна да сачува код алгоритма. Количина меморије потребна за унете податке. Количина меморије потребна за унесене податке (неке алгоритме, као што је сортирање, често само премештају подтаке који у унесени и није им потребан простор за излазне податке). Количина меморије потребне за радни простор током калкулације (ово укључујеу именоване променљиве и сваки стк простор потребан рутинама које се зову током калкулације; овај стек простор може бити врло важан за алгоритме који користе рекурзивне технике).