算法执行时间的渐进表示法

今天算法设计课上老师讲了算法执行时间的渐进表示法，首先复习了大$O$记号（$big\ O\ notation$）
其中，欧几里得辗转相除法（求最大公约数迭代算法）的渐近时间复杂度的计算并不是很好理解，这里先把结果贴出来： $O({log\ n}+{log\ m})$ .

使用的书是《算法设计与分析- C++语言描述（第3版）》电子工业出版社

1. 欧几里得迭代算法：

int Gcd(int m,int n)
{
    if(m==0) return n; if(n==0) return m; 
    /*
    卧槽，我是第一次发现如果两数中有零，最大公约数为另一个数
    */
    if(m>n) Swap(m,n); //交换两数位置，使得n大于m，其实这一步可有可无
    while(m>0)         //下次要试试若两数中有负数，算法的结果会变成怎样
    {
        int c=n%m;n=m;m=c;
        /*
        若迭代次数大于等于两次，当此迭代执行完毕后，
        m为本次迭代中n%m的值，n为上一次迭代n%m的值
        */
    }
    return n;   //返回m与n的最大公约数
}

2. 渐近时间复杂度的求解

这里先要证明一个引理

I. 定理

如果${n > m}$, 则$n\ mod\ m < \frac{n}{2}$

证明：

$if\ m \leq\frac{n}{2}$ ,则由于余数小于m，所以成立.
$if\ m >\frac{n}{2}, n-m<\frac{n}{2}$,即商为壹，余数为${n-m}$,所以成立.

Ⅱ.证明结论

书上写道：定理表明，两次迭代以后，余数最多是原始值的一半

余数至多是原始值的一半，这已经由定理显而易见的给出了，但“两次迭代以后”出现的很突兀，反正我是看不出来😂

这里我有两种想法来解释：

在有的版本中，欧几里得迭代算法是没有Swap()函数的，所以在输入数${n < m}$的情况下，第一次迭代的作用是交换两数位置，确保${n > m}$,这样第二次迭代所得${n\ mod\ m}$则可由定理得出小于$\frac{n}{2}$,这可以成为计算渐近时间复杂度的根据
但很遗憾的是，这个解释对于解释为何时间复杂度为$O(log\ n+log\ m)$似乎毫无帮助。（写到这里，我觉得有点好笑，因为我是从结论来反推这个结论是怎么推导出的，境界还是太低了，这根本从出发点开始就不对啊喂！😭）

下面写第二种想法（根据张成解释，不是我想出来的） 1.

首先，记住算法的返回参量是$n$
前面在算法部分我已经提到了，在每一次迭代中，我们会将取余这一步中的除数赋给$n$，将余数赋给$m$，$n$要经过两次迭代才会获得$n\ mod\ m$的值，
由算法可知最大公约数必定是一次迭代中所得的余数，所以，我认为两次迭代才完成了一次循环，只有第二次迭代完成后$n$得到了这次循环初$n\ mod\ m$的值（此时的$n$最多是最初$n$的一半），这次循环才算完成。
书上写的“定理表明”，余数最多是原始值的一半，这是否证明为使$n$为余数，必须要以两次迭代为单位？
最坏情况下，作为“被除数”的$m$（即每一次循环的第一次迭代的$m$，第二次迭代在我看来只是为了将余数赋给$n$，且将$m$变为循环开始时的“一半”【在最坏情况下】，毕竟这么理解的目的不就是为了向那个定理靠嘛）要被除以2的次数为$log\ m$，所以迭代要进行$2log\ m$次.

至于最终结果$O({log\ n}+{log\ m})$，问了老师我还是无法理解，这里贴出我的猜想：
当输入值$m,\ n$不确定大小关系时，渐进时间复杂度便无法计算，因为$log\ m,log\ n$可能不是一个数量级的，若$m>n$，渐近时间复杂度写$O(log\ m)$便是错误的，因为这时按上面的规范的话$n$起上面$m$的作用，为了保证式子的正确性，选择能够正确表达数量级的$O({log\ n}+{log\ m})$。

3. 查资料所得

很遗憾，网上对此算法的时间复杂度计算大多是对辗转相除法递归表达的讨论，对本文参考意义不大，即使是对本文所用算法的的讨论，它们的结果似乎是$O({log\ m})$（查资料到本文完成过了三天了，记不大清楚了，下次写这玩意儿得提升效率啊），也没有参考意义，不过推导方式好像有些不同，有兴趣的话日后可以再研究下，不过网上查资料的结果大多是不能轻信的😂

Essays