算法的时间复杂度和空间复杂度

目录算法的效率算法的复杂度时间复杂度概念大O的渐进表示法常见时间复杂度计算举例实例1实例2实例3实例4.计算strchr的时间复杂度实例5.BubbleSort的时间复杂度实例6.BinarySearch的时间复杂度实例7.阶乘递归Fac的时间复杂度实例8.斐波那契递归Fib的时间复杂度空间复杂度实例1计算BubbleSort的空间复杂度实例2计算Fibonacci的空间复杂度实例3计算阶乘递归Fac的空间复杂度常见复杂度对比算法的效率如何衡量一个算法的好坏看看下面的这个斐波那契数列long long Fib(int N) { if (N 3) return 1; return Fib(N - 1) Fib(N - 2); }斐波那契数列的递归实现方式非常简洁但简洁一定好吗那该如何衡量其好与坏呢该递归代码效率极低。因为它会重复计算大量子问题。例如计算Fib(5)时Fib(4)和Fib(3)都要各自再递归展开其中Fib(4)又会调用Fib(3)和Fib(2)……导致同一个数值如Fib(3)被多次重复计算。这种算法的时间复杂度是O(2^N)指数级N50 时已经慢到无法接受。空间复杂度是O(N)递归调用栈深度。相比之下用循环或动态规划实现斐波那契时间复杂度仅为O(N)效率高得多。简洁的不一定高效。衡量算法好坏要分析其时间复杂度和空间复杂度避免指数级爆炸的递归写法。时间复杂度运行时间随输入规模N的增长速度。比如递归斐波那契是 O(2^N)太慢。空间复杂度占用的额外内存随 N 的增长速度。递归版本因调用栈深度为 O(N)也较差。算法的复杂度算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般 是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算 机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度时间复杂度概念定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一 个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知 道但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法 的时间复杂度。即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度// 请计算一下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 执行的基本操作次数 F(N)N^22*N10N 10 F(N) 130N 100 F(N) 10210N 1000 F(N) 1002010实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这 里我们使用大O的渐进表示法。大O的渐进表示法大O符号Big O notation是用于描述函数渐进行为的数学符号。推导大O阶方法1、用常数1取代运行时间中的所有加法常数。2、在修改后的运行次数函数中只保留最高阶项。3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。使用大O的渐进表示法以后Func1的时间复杂度为O(N^2)N 10 F(N) 100N 100 F(N) 10000N 1000 F(N) 1000000通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况最坏情况任意输入规模的最大运行次数(上界)平均情况任意输入规模的期望运行次数最好情况任意输入规模的最小运行次数(下界)例如在一个长度为N数组中搜索一个数据x最好情况1次找到最坏情况N次找到平均情况N/2次找到在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)常见时间复杂度计算举例实例1基本操作执行了2N10次通过推导大O阶方法知道时间复杂度为 O(N)// 计算Func2的时间复杂度 void Func2(int N) { int count 0; for (int k 0; k 2 * N; k) { count; } int M 10; while (M--) { count; } printf(%d\n, count); }实例2基本操作执行了MN次有两个未知数M和N时间复杂度为 O(NM)// 计算Func3的时间复杂度 void Func3(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); }实例3基本操作执行了10次通过推导大O阶方法时间复杂度为 O(1)// 计算Func4的时间复杂度 void Func4(int N) { int count 0; for (int k 0; k 100; k) { count; } printf(%d\n, count); }实例4.计算strchr的时间复杂度strchr的标准实现逻辑——即在一个字符串中顺序查找某个字符最好情况是第一个字符就匹配1次操作最坏情况是遍历到末尾或找不到N 次操作N 为字符串长度。时间复杂度一般看最坏。因此时间复杂度为O(N)。// 计算strchr的时间复杂度 const char * strchr ( const char * str, int character );实例5.BubbleSort的时间复杂度基本操作执行最好N次最坏执行了(N*(N1)/2次通过推导大O阶方法时间复杂度一般看最 坏时间复杂度为 O(N^2)最好情况数组已经有序第一趟比较N-1次发现没有交换exchange保持为 0直接break退出循环。执行次数 N-1即O(N)。最坏情况数组完全逆序每一趟都要比较和交换。比较次数(N-1) (N-2) ... 1 N(N-1)/2即N(N-1)/2忽略常数和低阶项后为O(N²)。时间复杂度一般看最坏所以冒泡排序的时间复杂度为O(N²)。// 计算BubbleSort的时间复杂度 void BubbleSort(int* a, int n) { assert(a); for (size_t end n; end 0; --end) { int exchange 0; for (size_t i 1; i end; i) { if (a[i - 1] a[i]) { Swap(a[i - 1], a[i]); exchange 1; } } if (exchange 0) break; } }实例6.BinarySearch的时间复杂度基本操作执行最好1次最坏O(logN)次时间复杂度为 O(logN) pslogN在算法分析中表示是底 数为2对数为N。有些地方会写成lgN二分查找是在一个有序数组里找一个数x。过程先看数组最中间的数a[mid]如果它等于x就找到了如果x比它小就只去左边一半继续找如果x比它大就只去右边一半继续找重复以上步骤直到找到或者区间缩小到没有数字为止最好情况如果你运气爆棚第一次就猜中了中间那个数。那只需要1 次比较就结束了。所以最好时间复杂度是O(1)。最坏情况要找的数在数组最边上或者根本不在数组里。这时候你会一直缩小查找范围直到范围变成空。每次查找后剩下的数字个数大约是原来的一半刚开始有n个数字第一次比较后剩n/2个第二次比较后剩n/4个第三次比较后剩n/8个…直到最后剩下1个数字再查一次就确定有没有。问题来了从 n 变成 1你需要除以多少次 2这就是数学上的对数。假设 n 1616 → 8 → 4 → 2 → 1除了 4 次 2就到 1 了。这 4 就是 log₂(16) 4。更一般地需要比较的次数 ≈log₂(n)。所以最坏时间复杂度是O(log N)这里 log N 默认以 2 为底但底数不重要因为常数可以忽略。// 计算BinarySearch的时间复杂度 int BinarySearch(int* a, int n, int x) { assert(a); int begin 0; int end n - 1; // [begin, end]begin和end是左闭右闭区间因此有号 while (begin end) { //防止 (beginend)/2 直接加可能会溢出当 begin 和 end 都很大时。 // 1 就是除以 2位运算更快。不影响时间复杂度理解。 int mid begin ((end - begin) 1); if (a[mid] x) begin mid 1; else if (a[mid] x) end mid - 1; else return mid; } return -1; }实例7.阶乘递归Fac的时间复杂度基本操作递归了N次时间复杂度为O(N)。// 计算阶乘递归Fac的时间复杂度 long long Fac(size_t N) { if (0 N) return 1; return Fac(N - 1) * N; }实例8.斐波那契递归Fib的时间复杂度基本操作递归了2^N次时间复杂度为O(2^N)递归函数如果N 3也就是 N 1 或 2直接返回 1。否则它会调用自己两次Fib(N-1)和Fib(N-2)然后把两个结果相加。例如Fib(5)会去问Fib(4)和Fib(3)而每个又会继续往下拆直到Fib(1)或Fib(2)为止。为什么会很慢因为同一个中间结果会被重复计算无数次。我们拿Fib(5)举例Fib(3)被计算了两次。Fib(2)被计算了三次。Fib(1)被计算了两次。随着 N 增大重复计算量爆炸式增长。每次函数调用只要不是N3的终止情况它都会做一次加法Fib(N-1) Fib(N-2)。我们近似数一数函数调用的总次数。第一层调用 1 次Fib(N)第二层调用 2 次Fib(N-1)、Fib(N-2)第三层调用 4 次Fib(N-2) 的两个子调用等第四层调用 8 次…直到叶子节点N1 或 2为止。这像一个满二叉树大约有2^N量级的节点严格来说斐波那契递归树是接近 2^N但不是精确满的但大 O 只看数量级所以基本操作加法 递归调用的次数 ≈ 2^N 级别。最好情况N 很小比如 1 或 2直接返回O(1)。最坏情况也是我们要看的一般情况N 较大时递归调用次数 ≈ 2^N所以时间复杂度 O(2^N)。// 计算斐波那契递归Fib的时间复杂度 long long Fib(size_t N) { if (N 3) return 1; return Fib(N - 1) Fib(N - 2); }空间复杂度空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。实例1计算BubbleSort的空间复杂度使用了常数个额外空间所以空间复杂度为 O(1)额外开辟的变量只有end循环控制exchange标记是否发生交换i内层循环控制这些变量数量固定不会随着输入规模n变大而增多。无论n是 10 还是 10 万额外内存始终是几个字节。因此使用了常数个额外空间 → 空间复杂度 O(1)。// 计算BubbleSort的时间复杂度 void BubbleSort(int* a, int n) { assert(a); for (size_t end n; end 0; --end) { int exchange 0; for (size_t i 1; i end; i) { if (a[i - 1] a[i]) { Swap(a[i - 1], a[i]); exchange 1; } } if (exchange 0) break; } }实例2计算Fibonacci的空间复杂度动态开辟了N个空间空间复杂度为 O(N):空间复杂度分析动态开辟了一个长度为 n1 的 long long 数组数组占用的空间大小随输入 n 线性增长除此之外只用了常数个额外变量i 等因此空间复杂度为 O(N)// 计算Fibonacci的空间复杂度 // 返回斐波那契数列的前n项 long long* Fibonacci(size_t n) { if (n 0) return NULL; long long* fibArray (long long*)malloc((n 1) * sizeof(long long)); fibArray[0] 0; fibArray[1] 1; for (int i 2; i n; i) { fibArray[i] fibArray[i - 1] fibArray[i - 2]; } return fibArray; }实例3计算阶乘递归Fac的空间复杂度long long Fac(size_t N) { if (N 0) return 1; return Fac(N - 1) * N; }递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。空间复杂度为O(N)这里顺便理一下什么是栈帧每个函数被调用时计算机需要在内存中栈区记录一些信息函数的参数比如 N 的值函数返回后要去哪里继续执行返回地址函数的局部变量这里没有这块记录信息的内存区域就叫做“栈帧”。可以把栈帧想象成一张“任务纸条”调用函数时写一张纸条压在一摞纸条的最上面。函数返回时把最上面的纸条扔掉回到上一张纸条记录的位置。当你调用Fac(3)时它会这样执行Fac(3)调用Fac(2)等待Fac(2)的结果Fac(2)调用Fac(1)等待Fac(1)的结果Fac(1)调用Fac(0)等待Fac(0)的结果Fac(0)返回 1然后Fac(1)用 1 * 1 1 返回Fac(2)用 1 * 2 2 返回Fac(3)用 2 * 3 6 返回调用Fac(3)时栈帧的变化如下时刻栈中的栈帧从上到下深度刚开始空0调用 Fac(3)Fac(3)1Fac(3) 调用 Fac(2)Fac(2) → Fac(3)2Fac(2) 调用 Fac(1)Fac(1) → Fac(2) → Fac(3)3Fac(1) 调用 Fac(0)Fac(0) → Fac(1) → Fac(2) → Fac(3)4Fac(0) 返回删除 Fac(0)3Fac(1) 返回删除 Fac(1)2Fac(2) 返回删除 Fac(2)1Fac(3) 返回空0关键点在最深的时刻Fac(0)刚被调用但还没返回栈里有4 个栈帧N3 时深度为 4。当参数为 N 时递归会一直调用到 N0所以最多同时存在的栈帧个数 N 1从 N 到 0 一共 N1 层每一层栈帧占用的空间是常数因为只存参数 N 和返回地址等固定大小的信息。那么总占用的额外空间 (N1) × 常数 ≈N × 常数。在算法分析中常数忽略只关心规模 N所以空间复杂度为O(N)。常见复杂度对比一般算法常见的复杂度如下表达式大O表示阶名称5201314O(1)常数阶3n 4O(n)线性阶3n² 4n 5O(n²)平方阶3log₂ n 4O(log n)对数阶2n 3n log₂ n 14O(n log n)n log n 阶n³ 2n² 4n 6O(n³)立方阶2ⁿO(2ⁿ)指数阶