b'\n_START_ARTICLE_\nEvklidov algoritem\n_START_PARAGRAPH_\nEvkl\xc3\xaddov algor\xc3\xadtem je postopek, s katerim se dolo\xc4\x8di najve\xc4\x8dji skupni delitelj dveh \xc5\xa1tevil oziroma polinomov. Evklid je sicer prvotno zasnoval algoritem za dolo\xc4\x8danje najve\xc4\x8dje skupne mere dveh daljic._NEWLINE_Prednost Evklidovega postopka je, da ni potrebno razcepiti \xc5\xa1tevil. Sam postopek je sicer eden najstarej\xc5\xa1ih znanih algoritmov in je znan od pribli\xc5\xbeno leta 300 pr. n. \xc5\xa1t., verjetno pa je bil poznan \xc5\xbee 200 let prej.\n_START_SECTION_\nOpis algoritma\n_START_PARAGRAPH_\n\xc4\x8ce se obravnavata naravni \xc5\xa1tevili a in b, se predpostavi, da je a ve\xc4\x8dji ali enak b. \xc4\x8ce je b enak ni\xc4\x8d, potem je a rezultat postopka. Sicer pa se nadaljuje postopek s \xc5\xa1tevilom b in ter celo\xc5\xa1tevilskim ostankom deljenja a z b (a mod b)._NEWLINE_Zapis algoritma z rekurzijo:_NEWLINE__NEWLINE_ function gcd(a, b)_NEWLINE_     if b = 0 return a_NEWLINE_     else return gcd(b, a mod b)_NEWLINE_Analiza \xc4\x8dasa teka algoritma poka\xc5\xbee, da je najslab\xc5\xa1i mo\xc5\xbeen primer, kadar sta dve zaporedni Fibonaccijevi \xc5\xa1tevili, potreben \xc4\x8das je O(n) deljenj, kjer je n \xc5\xa1tevilo \xc5\xa1tevk na vhodu. Ker pa praviloma deljenje ni osnovna operacija, je potreben \xc4\x8das reda O(n\xc2\xb2).'