算法的时间复杂度推导方法

算法的时间复杂度推导方法

独立博客地址：chugang.net

语句频度

语句频度是指语句的重复执行次数。

推导大O阶方法

方法

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项相乘的乘数。

常数阶举例运用

右侧注释中的 num 表示语句执行的次数。

int sum = 0, n = 100;       /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
printf("%d", sum);          /* num = 1 */

这段代码的运行次数函数是 f(n) = 1 + 1 + 1 ，根据“推导大O阶方法”中的第一条规则，把
1 + 1 + 1 用 1 替换，运行次数函数变成了 f(n) = 1。该函数只有常数项，只需使用规
则1就可以推导出它即这段代码的时间复杂度是 O(1) 。

假如 sum = (n+1) * n / 2 执行3次，将上面的代码修改为:

int sum = 0, n = 100;       /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
printf("%d", sum);          /* num = 1 */

这段代码的运行次数函数是 f(n) = 1 + 1 + 1 + 1 + 1 。 按照推导大O阶第一条规则，用1取代
所有的加法常数，这段代码的运行次数函数是 f(n) = 1。这段代码的时间复杂度依然是 f(n) = O(1) 。

所有这类代码的时间复杂度都是 O(1)。O(1)叫做常数阶。不存在 O(2) 、 O(9) 这类写法。

线性阶举例运用

code-3

int i;
for(i = 0; i < n; i++){
    // 时间复杂度为O(1)的代码
}

code-3的运行次数函数是 f(n) = n * 1。加法常数为0个，跳过规则一。变量n的最高阶是 n * 1，无
其他项，跳过规则二。n * 1中的系数本来就是1，也可以直接跳过规则三，得到code-3的时间复杂度是
f(n) = O(n)。

code-4

int i;
for(i = 0; i < n; i++){
    // 时间复杂度为O(1)的代码
}

int j;
for(j = 0; j < m; j++){
    // 时间复杂度为O(1)的代码
}

code-4的运行次数函数是f(n) = n * 1 + m * 1。直接跳过规则一。n * 1 + m * 1有两个变量，
但次数都是1，任何一项 n * 1 或 m * 1 都可视为最高价，根据推导规则二“保留最高阶”，得出
运行次数函数是f(n) = n * 1 或 f(n) = m * 1。最后根据规则三，得出code-4的时间复杂度是
f(n) = O(n)。

对数阶举例运用

code-5

int count = 1;
while(count < n){
    count = count * 2;
    //其他时间复杂度为O(1)的代码 
}

code-5似乎不能用前面的推导大O阶方法来分析时间复杂度，我从《数据结构与算法分析》P21找到了分析
"运行时间中的对数"的一般法则。这个一般法则是：

如果一个算法用常数时间(O(1)将问题的大小削减为其一部分（通常是1/2），那么该算法就是 O(log N)。
另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是 O(N) 。

code-5中，假设 n = 8 ，初始化时，while(count < n) 需要运行8次。经过一次循环后，count变为2，
循环需要运行4次，变为原来的一半。根据那条一般法则，判断 code-5 的时间复杂度是 O(log N)。

将code-5修改为code-6，

int count = 1;
while(count < n){
    count = count + 2;
    //其他时间复杂度为O(1)的代码 
}

code-6每次执行循环后，会把问题减少2个常数，时间复杂度应为 O(N)。

若将code-6中的count = count + 2改为code = count - 2，时间复杂度仍然是 O(N)。但我有点理解不了。

平方价举例运用

code-7

int i, j;   /*1*/
for(i = 0; i < n; i++){ /*2*/
    for(j = 0; j < n; j++){ /*3*/
        //时间复杂度为O(1)的代码 /*4*/
    }   /*5*/
}   /*6*/

code-7中第二个循环体的时间复杂度是O(N)。第一个循环体将第二个循环体再执行N次，时间复杂度变为O(N2)。
如果将第二个循环体中的n改为m，那么code-7的时间复杂度就是O(N*M)。注意，O(N*M)和O(N2)都叫做
平方阶，二者实质相同。

多层循环体的时间复杂度就是每层循环体的运行次数相乘。

code-8

int i, j;
for(i = 0; i < n; i++){
    for(j = i; j < n; j++){
        //时间复杂度为O(1)的代码
    }
}

code-8运行次数是(n+1)*n*n/2。只保留最高阶并且去掉它的系数，时间复杂度是O(N2)。有些地方理解不了。

code-9

void function(int count){

    int j;
    
    for(j = count; j < n; j++){
    
        printf("%s", "hello,world");
        
    }
}

n++;        /* num = 1 */

function(n);    /* num = n */

int i,j;    /* num = 1 */

for(i = 0; i < n; i++){     /* num = n*n */
    
    function(i);
    
}

for(i = 0; i < n; i++){         /* num = (n+1)*n/2 */
    
    for(j = i; j < n; j++){
        
        printf("%s", "hi");
        
    }
}

code-9的时间复杂度是多少呢？

首先将每行代码的执行次数标出来。

code-9的执行次数（首先忽略掉常数项）是n + n*n + (n+1)*n/2，计算结果为1.5*n*n + 2*n。
只保留最高阶1.5*n*n，最后将系数变为1，执行次数为n*n，时间复杂度为O(N2)。

这种方法有不确定性的因素存在，或者说，在计算执行次数的时候，使用了互相矛盾的方法。

独立博客地址：chugang.net

重新思考之后，发现并不存在矛盾，而是《大话数据结构》中推导时间复杂度的方法有小缺陷。这个推导
本身就是一种粗略估计，为何在推导过程中有时又在进行精确计算呢？以code-8为例，该书使用了精确
的计算方法。若全部都坚持使用粗略估计计算，那么计算过程是这样的：code-8中第二个循环体的运行
次数是N，或者抽象为“一个变量”，第一个循环体的运行次数也是N或M，也抽象为“一个变量”，整体的运行
次数为两个变量相乘，即时间复杂度为O(N2)。这种粗略估计计算方法，建立的基础是：影响循环执行次数
的变量只有那个与循环终止条件相关的变量，与起始变量无关。

这种方法，又不能适用于对数阶的时间复杂度推导。或许，对数阶中的循环，本来就是一种特殊情况，不能
采用普通循环的推导方法。此处存疑。*

常见的时间复杂度

直接摘抄《大话数据结构》中的有关部分。

常见的时间复杂度

理解不了这些时间复杂度所耗时间的顺序，应该如何比较它们所耗时间？

独立博客地址：chugang.net