Evklidov algoritem: Razlika med redakcijama

dodanih 71 zlogov ,  pred 12 leti
m
dp
m (vrnitev sprememb uporabnika »194.249.197.2« (pogovor) na zadnje urejanje uporabnika »JAnDbot«)
m (dp)
'''Evklidov algoritem''' [evklídov algorítem] je [[algoritem|postopek]], s katerim določimo [[največji skupni delitelj]] dveh [[število|števil]] oz.oziroma [[polinom]]ov. [[Evklid]] je sicer prvotno je zasnoval algoritem za določanje največje skupne mere dveh [[daljica|daljic]].
 
Prednost Evklidovega postopka je, da ni potrebo [[faktorizacija|razcepiti števil]]. Sam postopek je sicer eden najstarejših znanih algoritmov, datirain okrogje znan od približno leta [[300. pr. n. št.]], verjetno pa je bil poznan že 200 let prej.
 
== Opis algoritma ==
 
Če imamo naravni števili ''a'' in ''b'', predpostavimo, da je ''a'' večji ali enak ''b''. Če je ''b'' enak nič, potem je ''a'' rezultat postopka. Sicer pa nadaljujemo postpek s številom ''b'' in ter celoštevilskim ostankom deljenja ''a'' z ''b'' ( a ''[[modulo|mod]]'' b).
 
Analiza časa teka algoritma pokaže, da je najslabši možen primer, kadar imamo dve zaporedni [[Fibonaccijeva števila|Fibonaccijevi števili]], potreben čas je [[Zapis 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 plus plus|C++]] implementacija ==
<pre><nowiki>
int gcd(int a, int b) {
if (b == 0)
return a;
 
return gcd(b, a % b);
}
</nowiki></pre>
 
Ali [[iteracija|iterativna]] različica:
 
<pre><nowiki>