Giải thuật Euclid tìm USCLN

Chào admin ạ.

Em đang gặp rắc rối với việc tính độ phức tạp của giải thuật Euclid. Thường thì tính độ phức tạp có vòng lặp FOR thì em đếm số lần lặp được, còn Euclid thì thuật toán nó chia. Em không biết tính sao cả.

Xin admin giúp em giải quyết bài toán này với.

int USCLN(int m, int n){
r = m%n;
while(r)
{
m = n;
n = r;
r = m%n;
}
return n
}

Em cám ơn rất nhiều ạ.!

khanhxuyencm đã viết:

Chào admin ạ.

Em đang gặp rắc rối với việc tính độ phức tạp của giải thuật Euclid. Thường thì tính độ phức tạp có vòng lặp FOR thì em đếm số lần lặp được, còn Euclid thì thuật toán nó chia. Em không biết tính sao cả.

Xin admin giúp em giải quyết bài toán này với.

Code:

int USCLN(int m, int n){
    r = m%n;
    while(r)
    {
      m = n;
      n = r;
      r = m%n;
    }
    return n
}


Em cám ơn rất nhiều ạ.!