数据结构有关问题，关于欧几里德算法的时间复杂度，求解

数据结构问题，关于欧几里德算法的时间复杂度，求解~
是《数据结构与算法分析：c语言描述 原书第二版》mark allen weiss 中的问题：

原话：
   计算最大公约数的欧几里德算法.两个整数的最大公约数（Gad）是同时整除二者的最大整数。于是，Gcd（50，15）=5.下面是算法：（假设M>=N）

unsigned int Gcd(unsigned int M, unsigned int N)
{
    unsigned int Rem;
    while(N>0)
    {
       Rem = M % N;
       M = N;
       N = REM
     }
     return M:

}

算法通过连续计算余数直到余数为0为止，最后的非零余数就是最大公约数。因此如果M=1989，N=1590，则余数序列是399，393，6，3，0.从而，Gcd（1989，1590）=3.
   如前所述，估计算法的整个运行时间依赖于确定余数序列究竟有多长。虽然LogN看似是理想中的答案，但是根本看不出余数的值按照常数因子递减的必然性，因为我门看到，例中的余数是300仅仅降到393.事实上，在一次迭代中余数并不按照一个常数因子递减。然而我们可以证明，在两次迭代以后，余数最多是原始值的一半。这就证明了，迭代次数至多是2logN = O(logN)从而得到运行时间。这个证明并不难。。。。。省略。


我想问的是“迭代次数至多是2logN”，为什么是2logN，这个2是从哪来的，一直想不通~~

需要书的我可以发给你们看，，， 数据结构 算法 c语言 迭代 gcd
[解决办法]

引用:

这个证明我也知道，我只是不明白，2logN是怎么来的。。。

假定你要求的数初始是m0和n0，且后续队列为
m0, m1, ... m2k, ... me
n0, n1, ... n2k, ... ne
且每一对下标相同的数都满足 mi <= ni
2 = 1 * 2次迭代后的2个数应该满足 m2 < n2 < max(m0, n0) / 2
4 = 2 * 2次迭代后的2个数应该满足 m4 < n4 < max(m2, n2) / 2 < max(m0, n0) / 4
6 = 3 * 2次迭代后的2个数应该满足 m6 < n6 < max(m4, n4) / 2 < max(m0, n0) / 8
... 4，8分别对应 2^2和2^3
2k= k * 2次迭代后2个数应该满足 m2k < n2k < max(m2k-2, n2k-2) / 2 < max(m0, n0) / (2^k)

当max(m0, m0) / (2^k) = 1即max(m0, n0) = 2^k时，迭代明显结束
k = log(max(m0, n0))

总共迭代次数是2k = 2log(max(m0, n0)) = 2logN

查看更多 下一篇