Informatică, întrebare adresată de Rayzen, 8 ani în urmă

Care este complexitatea în timp (time complexity) a algoritmului din imagine?

Eu cred ca e O(log n), dar nu știu cum să arăt asta.

Anexe:

Rayzen: Nicomachus e de fapt acum vazui

CinevaFaraNume: Stiu ca se numeste algoritmul pentru cmmdc prin scaderi repetate

CinevaFaraNume: Prima oara cand aud de un nume

Rayzen: Mersi !
Dar nu stiu cum sa demonstrez.

Rayzen: Nu stiu cine are creditele.
Cred ca Euclid.

Rayzen: pentru metoda cu scaderi succesive

CinevaFaraNume: Pentru demonstrare trebuie sa cauti cel mai rau caz: cel in care faci cele mai multe iteratii

CinevaFaraNume: De acolo vezi cate iteratii faci in functie de datele de intrare si aia e complexitatea

Rayzen: cel mai rau caz are max(n,m) apelari

Rayzen: fiindca e cum ai zis (m,1) sau (1,n)

Răspunsuri la întrebare

Răspuns de cosmaandra2000

Explicație:

Hey ! Uite, m-am mai consultat si cu altcineva si ceva de genul acesta vine. Normal eu credeam ca este O(n) ca par n pasi, ca n-avem while-uri, n-avem for-uri. Dar e chiar mai mica. Trebuie sa iti dai exemple si apoi vezi cati pasi se fac pe fiecare. Si din ce m-am uitat si eu prin caiet, nu prea este alta varianta, log n zic eu ca nu are de unde.

Anexe: