C语言学习20：算法的复杂度

算法的复杂度

算法在编译成可执行程序后，运行时需要耗费 时间资源(执行次数) 和 空间资源(内容) 。因此衡量一个算法的好坏，一般是从 时间和空间两个维度来衡量的，即 时间复杂度和空间复杂度

时间复杂度

1. 定义

• 时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例

• 算法中的基本操作的执行次数，为算法的时间复杂度。

• 即：找到某条基本语句与问题规模 N 之间的数学表达式，就是算出了该算法的时间复杂度

2. 举例

计算一下 func1 中 ++count 语句执行了多少次

void func1(int n){
    int count = 0;
    
    // 两层循环
    for (int i = 0;i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            ++count;
        }
    }
    // 单层循环
    for (int k = 0; k < 2 * n; k ++) {
        ++ count;
    }
    // 循环
    int m = 10;
    while (m--) {
        ++count;
    }
    printf("%d\n",count);
}

结果：
func1 的时间复杂度：func1(n) = n * n + 2 * n + 10
n = 10：func1(10) = 10 * 10 + 2 * 10 + 10 = 130

实际我们计算时间复杂度时，起始并不一定要计算精准的执行次数，只需要计算 大概执行次数，那么这里我们使用大 O 的渐进表示法

大 O 的渐进表示法

1. 定义

大O符号（Big O notation）：是用于 描述函数渐进行为的数学符号。

2. 推导大O阶方法：

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项
• 如果最高阶项存在且不是1，则去掉与这个项目相乘的常数。得到的结果就是大O阶

3. 另外有些算法的时间复杂度存在最好、平均和最坏情况：

• 最坏情况：任意输入规模的最大运行次数(上界)
• 平均情况：任意输入规模的期望运行次数
• 最好情况：任意输入规模的最小运行次数(下界)

例如：

在一个长度为 N 数组中搜索一个数据 x

• 最好情况：1 次找到
• 最坏情况：N 次找到
• 平均情况：N/2 次找到

在实际中一般情况关注的是算法的 最坏 运行情况，所以数组中搜索数据时间复杂度为 O(N)。

注：时间复杂度是不固定的，时间复杂度表示的是 最坏 的情况。

4. 实例

Q：计算下面代码的时间复杂度

void func2(int n, int m) {
    int count = 0;
    for (int k = 0; k < m; k ++) {
        ++count;
    }
    for (int k = 0; k< n; k ++) {
        ++count;
    }
    printf("%d\n",count);
}
=====
20

结果：
时间复杂度：O(m+n)
这里除非说明 m>>n 或 n>>m，远小于的那个字母就可以不表示了

Q：计算下面代码的时间复杂度

void func3(int n) {
    int count = 0;
    for (int k = 0; k < 100; k ++) {
        ++count;
    }
    printf("%d\n",count);
}

====
100

结果：
时间复杂度：O(1)
分析：这里的 1 不是一次，是代表常数次，常数次用 O(1) 表示，写成1亿也是常数

常见时间复杂度计算举例

1. 冒泡排序

• 冒泡排序的思想：相邻两个元素比较，取到最大值放在最后，共进行 n-1 趟

第一趟：n-1 次
第二趟：n-2 次
…
最后一趟：1 次

• 我们发现上面是一个 等差数列，等差数为1，利用等差数列公式求和 (首项 + 末项) * 项数 / 2

注：等差数列 即 每一项与它的前一项的差等于同一个常数，这个数列就叫做 等差数列
求和公式：`(首项 + 末项) * 项数 / 2

利用公式计算：1 + 2 + 3 + … + n-1 = (1 + n-1) * (n-1) / 2

最坏的结果（执行次数）： n^2

因此：冒泡排序 的时间复杂度 O(n^2)

• 具体实现

#include <stdio.h>

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void bubbleSort(int *arr, int n) {
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n - i - 1; j ++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
    
    // 打印
    for (int i = 0; i < n; i ++) {
        printf("%d\n",arr[i]);
    }
}

int main(int argc, const char * argv[]) {
    int arr[5] = {5,4,3,2,1};
    int len = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, len);
    
    return 0;
}

2. 阶乘递归

• 代码实现

// 求 n! 传入一个无符号整型
int factorial(int n){
    if (n<=1){
        return 1;
    }
    return n * factorial(n-1);
}

int main(int argc, const char * argv[]) {
    int n = 5;
    printf("%d 的阶乘是：%d\n",n,factorial(n));
    //5 的阶乘是：120
    return 0;
}

这是一个递归调用，递归了 n 次

结论：因此时间复杂度是 O(n)

3. 二分查找

• 代码实现

int binarySearch(int *arr, int n, int x) {
    int begin = 0;
    int end = n - 1;
    while (begin <= end) {
        int mid = (end - begin) / 2;
        if (arr[mid] < x) {
            begin = mid + 1;
        }else if (arr[mid] > x) {
            end = mid - 1;
        }else {
            return mid;
        }
    }
    return -1;
}

int main(int argc, const char * argv[]) {
    int arr[5] = {1,2,3,4,5};
    int len = sizeof(arr)/sizeof(arr[0]);
    int index = binarySearch(arr, len, 3);
    printf("%d\n",index);
    
    return 0;
}
====
2

注：
logN 的意思是以 2 为底 多少次幂 等于 N

分析：二分查找是对数组区间不断的缩小 1/2 找数字

第1次：N/2
第2次：N/2^2
...
第x次：N/2^x

假设二分了X次，有 1 * 2 * 2…. * 2 = N，2^X=N, X=(log2) N

• 因此，二分查找的时间复杂度 O(logN)