欧几里得算法时间复杂度分析

欧几里得算法，也叫辗转相除法，其时间复杂度可以通过递归树来分析。

假设两个数 a 和 b 满足 a > b，递归过程可以表示为：

gcd(a, b) = gcd(b, a mod b)

每次递归都会将一个数缩小为原来的一半，因此递归树的高度为 log a（以 2 为底）。在每个节点上，计算 a mod b 的时间复杂度为 O(1)，因此每个节点的时间复杂度也为 O(1)。

因此，总时间复杂度为 O(log a)。