• 数据结构与算法之时间复杂度和空间复杂度（C语言版）

    1. 时间复杂度

    1.1 概念

    简而言之，算法中的基本操作的执行次数，叫做算法的时间复杂度。也就是说，我这个程序执行了多少次，时间复杂度就是多少。

    比如下面这段代码的执行次数：

    1. void Func1(int N)
    2. {
    3.     int count = 0;
    4.     for (int i = 0; i < N ; ++ i)
    5.     {
    6.         for (int j = 0; j < N ; ++ j)
    7.         {
    8.             ++count;
    9.         }
    10.     }
    11.  
    12.     for (int k = 0; k < 2 * N ; ++ k)
    13.     {
    14.         ++count;
    15.     }
    16.     int M = 10;
    17.     while (M--)
    18.     {
    19.         ++count;
    20.     }
    21.     printf("%d\n", count);
    22. }

    Func1执行的基本操作次数：

    F(N) = N^2 + 2*N + 10

    在这里两层for循环的次数是N^2，第二个for循环的次数是2*N，while循环的次数是10
    所以这个算法中的基本操作次数就是 N^2 + 2*N + 10。

    那我们的时间复杂度就是这个吗，其实不是的。实际上我们在计算时间复杂度的时候，我们并不一定要计算精确的执行次数，而只需要大概执行次数。

    这又是为什么呢？

    当N = 10的时候，F(N) = 130

    当 N = 100 的时候，F(N) = 10210

    当 N = 1000 的时候，F(N) = 1002010

    我们发现当N趋于无穷大的时候，对F(N)影响最大的是N^2，这就跟我们在数学里找极限一样，抓大头，找影响最大的一项，用影响最大的一项来表示我们的时间复杂度

    这种表示方法我们称作大O的渐进表示法。

    1.2大O的渐进表示法
     

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

    基本执行次数用大O阶方法表示的规则：
     

    1. 如果执行次数中出现加法常数（无论多大，只要是常数），用1来代替。

    2. 如果执行次数是多项式，执行次数只保留最高阶项（最高次项）

    3. 如果最高阶项存在且不是1，舍去系数。

    4.经过1，2，3操作得到的结果就是大O阶表示。

    所以我们上面的F(N) = N^2 + 2*N + 10 用大O阶表示就是 O(N^2)。
     

    1.3 最好，平均，最坏情况

    有些算法的时间复杂度是存在最好，平均，最坏情况的。

    1.最好情况：基本操作次数的最小值

    2.平均情况：期望的基本操作次数

    3.最坏情况：基本操作次数的最大值

    但是在实际中我们都是用最坏情况来表示时间复杂度

    1.4 时间复杂度例题

    1.4.1 例题1

    1. void Func2(int N)
    2. {
    3.     int count = 0;
    4.     for (int k = 0; k < 2 * N ; ++ k)
    5.     {
    6.         ++count;
    7.     }
    8.     int M = 10;
    9.     while (M--)
    10.     {
    11.         ++count;
    12.     }
    13.     printf("%d\n", count);
    14. }

    答案：O(N)

    基本执行次数是（2 * N + 10），用大O阶表示为O(N)

    1.4.2 例题2

    1. void Func3(int N, int M)
    2. {
    3.     int count = 0;
    4.     for (int k = 0; k < M; ++ k)
    5.     {
    6.         ++count;
    7.     }
    8.     for (int k = 0; k < N ; ++ k)
    9.     {
    10.         ++count;
    11.     }
    12.     printf("%d\n", count);
    13. }

    答案：O(M+N)

    基本执行次数是M+N次，由于有两个未知数M和N，所以大O阶表示为O(M+N)

    1.4.3 例题3

    1. void Func4(int N)
    2. {
    3.     int count = 0;
    4.     for (int k = 0; k < 100; ++ k)
    5.     {
    6.         ++count;
    7.     }
    8.     printf("%d\n", count);
    9. }

    答案：O(1)

    基本执行次数是100次，用大O阶表示为O(1)

    1.4.4 例题4

    1. void BubbleSort(int* a, int n)
    2. {
    3.     assert(a);
    4.     for (size_t end = n; end > 0; --end)
    5.     {
    6.         int exchange = 0;
    7.         for (size_t i = 1; i < end; ++i)
    8.         {
    9.             if (a[i-1] > a[i])
    10.             {
    11.                 Swap(&a[i-1], &a[i]);
    12.                 exchange = 1;
    13.             }
    14.         }
    15.         if (exchange == 0)
    16.             break;
    17.     }
    18. }

    答案：O(N^2)

    基本操作次数是(n-1)+(n-2)+(n-3)+....+3+2+1 = ((n + 1) * n) / 2

    最好情况就是遍历一次就排序成功，基本操作次数是n-1，大O阶表示是O(N)

    最坏情况就是全部遍历完，基本操作次数是((n + 1) * n) / 2，大O阶表示为O(N^2)

    时间复杂度一般看最坏情况，为O(N^2)

    大O表示为O(N^2)

    1.4.5 例题5

    1. int BinarySearch(int* a, int n, int x)
    2. {
    3.     assert(a);
    4.     int begin = 0;
    5.     int end = n-1;
    6.     // [begin, end]：begin和end是左闭右闭区间，因此有=号
    7.     while (begin <= end)
    8.     {
    9.         int mid = begin + ((end-begin)>>1);
    10.         if (a[mid] < x)
    11.             begin = mid+1;
    12.         else if (a[mid] > x)
    13.             end = mid-1;
    14.         else
    15.             return mid;
    16.     }
    17.     return -1;
    18. }

    答案：O(log N)

    这个算法是二分查找

    最好情况是查找一次，为O(1)

    最坏情况是begin = end 了，只剩了一个元素，我们可以设循环的次数是x，一次循环我们是砍掉了一半的数组元素，那到最后没有元素了，说明n / 2^x = 1  

    所以x = log n(以2为底)。时间复杂度的大O阶表示就是O(logN)。

    我们规定以2为底的对数函数写成 log N 

    1.4.6 例题6

    1. long long Fac(size_t N)
    2. {
    3.     if(0 == N)
    4.         return 1;
    5.  
    6.     return Fac(N-1)*N;
    7. }

    答案：O(N)

    基本操作次数：这个函数一共递归了N次，时间复杂度就是O(N)

    1.4.7 例题7

    1. long long Fib(size_t N)
    2. {
    3.     if(N < 3)
    4.         return 1;
    5.  
    6.     return Fib(N-1) + Fib(N-2);
    7. }

    答案：O(2^N)

    基本操作次数：这个函数递归了1+2+4+8+... 是一个不完整的等比数列，在N<3之后不会递归，但是不影响整体的趋势，可以忽略不计，这个等比数列的和是2^n - 1

    所以大O阶表示为O(2^n)

    2.空间复杂度

    2.1概念

    空间复杂度指的是临时占用存储空间大小的量度，需要注意的是空间复杂度并不是程序占了多少个字节的空间，因为没有什么太大意义
    ​​​​​​​所以空间复杂度指的是新创建的变量个数，也是额外开辟的空间。
    也就是说你为了完成一个算法，必须开的空间不算空间复杂度里，但是你为了解决算法，你又去开辟的空间才算空间复杂度。

    空间复杂度计算规则和时间复杂度基本一致，用大O阶渐渐表示法。

    注意⚠️⚠️⚠️：

    1. 计算空间复杂度时，一般不需要考虑函数的形式参数。空间复杂度主要关注的是算法执行过程中所占用的额外空间，而函数的形式参数在函数调用时会被压入调用栈中，属于函数调用过程中的内存分配，并不计入空间复杂度的计算。

    2. 递归算法在每次递归调用时需要维护函数调用栈，而函数调用栈会占用额外的内存空间，所以其空间复杂度为递归所使用的堆栈空间的大小。

    2.2 空间复杂度例题

    2.2.1 例题1

    1. void BubbleSort(int* a, int n)
    2. {
    3.     assert(a);
    4.     for (size_t end = n; end > 0; --end)
    5.     {
    6.         int exchange = 0;
    7.         for (size_t i = 1; i < end; ++i) 
    8.         {
    9.             if (a[i - 1] > a[i]) 
    10.             {
    11.                 Swap(&a[i - 1], &a[i]);
    12.                 exchange = 1;
    13.             }
    14.         }
    15.         if (exchange == 0)
    16.             break;
    17.     }
    18. }

    这个冒泡排序临时创建的变量分别是 end ， exchange 和 i  一共三个，是常数个。

    所以空间复杂度用大O阶表示为O(1)

    2.2.2 例题2

    1. long long* Fibonacci(size_t n)
    2. {
    3.     if(n==0)
    4.         return NULL;
    5.  
    6.     long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
    7.     fibArray[0] = 0;
    8.     fibArray[1] = 1;
    9.     for (int i = 2; i <= n ; ++i)
    10.     {
    11.         fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    12.     }
    13.     return fibArray;
    14. }

    这个算法我们直接看新创建的变量是fibArray这个数组，是动态开辟的一个数组，开辟了n+1个空间，还有个i变量，一共是n+2个变量。

    用大O阶表示为O(n)

    2.2.3 例题3

    1. long long Fac(size_t N)
    2. {
    3.     if(N == 0)
    4.         return 1;
    5.  
    6.     return Fac(N-1)*N;
    7. }

    首先我们要明确的是这是一个函数递归调用

    我们函数递归一共要递归N次，共创建新的栈空间N个

    所以空间复杂度为O(N)

    2.2.4 例题4

    1. long long Fib(size_t N)
    2. {
    3.     if(N < 3)
    4.         return 1;
    5.  
    6.     return Fib(N-1) + Fib(N-2);
    7. }

    此时的空间复杂度是多少呢？ O(2^N)？ 还是O(N)？

    我们画图来说明

    我们来看这个函数的递归调用并不是同时进行的，而是先调用左边的，左边调用完了，最下面Fib（2）往回销毁空间之后才去调用Fib（1），也就是在这个时候才开辟Fib（1）的空间

    蓝色箭头代表从Fib（3）到Fib（2）先开辟Fib（2）的栈空间，当调用结束的时候，这段空间就要销毁，于是就有了红色的箭头代表销毁Fib（2）的空间，销毁之后我们才开始调用Fib（1），绿色箭头代表调用Fib（1），此时就要开辟Fib（1）的空间，要知道的是我们刚刚销毁一个栈空间，现在又要开辟一个栈空间，所以空间是被重复利用的，也就是黄色的箭头，Fib（1）的空间跟Fib（2）的空间是同一块空间。

    所以我们真正开辟的空间只有从Fib（N）到Fib（2）这一段，其他的调用函数，都是在重复利用栈空间的过程。

    所以空间复杂度是O(N)

    总结：时间是累积的，一去不复返
                    空间是可以重复利用的。 

    3.常见复杂度的对比

    常数阶O(1)5201314
    线性阶O(N)3N+1
    平方阶O(N^2)2N^2 + 3N + 1
    对数阶O(logN)3log(2)N + 2
    NlogN阶O(NlogN)2N+3Nlog(2)N + 1
    立方阶O(N^3)3N^3+2N^2+N+1
    指数阶O(2^N)2^N
    O(1)  <  O(log n)  <  O(n)  <  O(nlogn)  <  O(n^2)  <  O(n^3)  <  O(2^n)  <  O(n!)  <  O(n^n)
  • 相关阅读:
    个人对高等数学极限的理解1
    Git及Github初学者教程
    python+django高校澡堂洗浴浴室预约签到管理系统8d8c
    实现vue项目和springboot项目前后端数据交互
    TiDB Lightning 并行导入
    这种考勤方式，居然能轻松实现！
    xss挑战之旅11-19关
    SpringCloud之Feign
    java spring cloud 企业电子招标采购系统源码:营造全面规范安全的电子招投标环境，促进招投标市场健康可持续发展
    iPhone 15首批体验出炉，掉漆、烫手、进灰，口碑严重崩塌
  • 原文地址：https://blog.csdn.net/2302_76941579/article/details/133202680