Evklidov algoritem: Razlika med redakcijama

dodanih 35 zlogov ,  pred 4 leti
m
m/dp/slog/+p
m (vrnitev sprememb uporabnika 109.182.152.204 (pogovor) na zadnje urejanje uporabnika SportiBot)
m (m/dp/slog/+p)
'''Evklídov algorítem''' je [[algoritem|postopek]], s katerim določimose določi [[največji skupni delitelj]] dveh [[število|števil]] oziroma [[polinom]]ov. [[Evklid]] je sicer prvotno zasnoval algoritem za določanje največje skupne mere dveh [[daljica|daljic]].
 
[[Slika:Euclidean algorithm running time X Y.png|thumb|right|230px|Graf za čas izračunavanja [[največji skupni delitelj|D(''x'',''y'')]]. Rdeča označuje hitro izračunavanje, bolj modre točke pa označujejo počasnejše]]
 
== Opis algoritma ==
 
Če imamose obravnavata naravni števili ''a'' in ''b'', predpostavimose predpostavi, da je ''a'' večji ali enak ''b''. Če je ''b'' enak nič, potem je ''a'' rezultat postopka. Sicer pa nadaljujemose nadaljuje postopek s številom ''b'' in ter celoštevilskim [[deljenje z ostankom|ostankom deljenja]] ''a'' z ''b'' (a ''[[modulo|mod]]'' b).
 
Zapis algoritma z [[rekurzija|rekurzijo]]:
'''else''' '''return''' gcd(b, a '''mod''' b)
 
Analiza časa teka algoritma pokaže, da je najslabši možen primer, kadar imamosta dve zaporedni [[Fibonaccijeva števila|Fibonaccijevi števili]], potreben čas je [[Zapiszapis veliki O|''O''(''n'')]] deljenj, kjer je ''n'' število števk na vhodu. Ker pa praviloma deljenje ni osnovna operacija, je potreben čas reda ''O''(''n''²).
 
== Zapis algoritma v jezikih [[Programski jezik C|C]] in [[C++]] ==