# 算法效率评估 - 时间效率：算法运行的时间长短（时间复杂度） - 空间效率：算法占用内存空间的大小（空间复杂度） # 迭代与递归 ## 迭代 1. for循环 ```cpp int forLoop(int n) { int res = 0; for (int i = 1; i <= n; ++i){ res += i; } return res; } ``` 此函数的操作数量与输入数据大小n成正比。 2. while循环 ```cpp int wileLoop(int n) { int res = 0; int i = 1; while (i <= n) { res += i; i++; } return res; } ``` 个人感觉都差不多，因为go语言只有for循环，说明for循环能代替大部分循环了 3. 嵌套循环 ```cpp string nestedForLoop(int n) { ostringstream res; for(int i = 1; i <= n; ++i){ for(int j = i; j <= n; ++j){ res << "(" << i << ", " << j << "),"; } } return res.str(); } ``` 这种情况下，函数的操作数量与$n^2$ ## 递归递归就是函数自己调用自己，然后会触发终止条件，开始逐层返回 ```cpp int recur(int n) { if (n == 1){ return 1; } int res = recur(n - 1); return n + res; } ``` 从计算角度看，迭代和递归可以得到完全相同的结果。但是它们的分别代表了不同的解决问题范式。 - 迭代：自下而上，从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成 - 递归：自上而下，将原问题分解成为更小的子问题，这些子问题和原问题具有相同的形式。 ### 1.调用栈每次函数调用自身时，相同都会为函数开辟新的空间，储存函数局部变量、调用地址和其他信息等。这会导致两个方面的结果。 - 函数的内存空间只有函数完全返回时才会释放，因此递归通常比迭代更加耗费内存。 - 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。在实际应用中，编程语言的递归深度是有限的，过深递归可能会导致栈溢出错误。 ### 2.尾递归如果函数中返回前最后一步才进行递归调用，则函数可以被编译器或解释器优化，使其空间效率上和迭代相当。这种情况称为`尾递归` - 普通递归：当函数返回到上一层函数后，需要继续执行代码，因此系统需要保持上一层调用的上下文 - 尾递归：递归调用时函数返回前最后一个操作，这意味着函数返回到上一层后，无须继续执行其他操作，因此系统无需保存上一层函数的上下文 ```cpp // 尾递归例子 int tailRecur(int n, int res) { if(n == 0) return res; return tailRecur(n - 1, res + n); } ``` ### 3.递归树当处理与分治相关的算法问题时，递归往往比迭代的思路更加直观、代码更加易读。以斐波那契数列为例： ```cpp // 递归写法 int fib(int n) { if(n == 1 || n == 2) return n -1; int res = fib(n - 1) + fib(n - 2); return res; } ``` ```cpp // 迭代写法 int fib2(int n){ if(n == 1 || n == 2) return n - 1; int a = 0, b = 1, res; for(int i = 3; i <= n; ++i){ res = a + b; a = b; b = res; } return res; } ``` 递归的工作机制就是先入后出，所以我们可以用显式的栈（迭代）去模拟递归的行为。从而将递归转换为迭代形式。 ```cpp int forLoopRecur(int n) { stack stack; int res = 0; // 递归调用 for(int i = n; i > 0; i--){ stack.push(i); } while(!stack.empty()){ // 通过出栈来模拟归 res += stack.top(); stack.pop(); } return res; } ``` ## 时间复杂度时间复杂度不是具体的算法运行时间，而是随着数据量的增大算法运行时间也会随趋势增大。 ```cpp // 算法 A 时间复杂度：常数阶 void algorithm_A(int n){ cout << 0 << endl; } // 算法 B 的时间复杂度: 线性阶 void algorithm_B(int n){ for(int i = 0; i < n; i++){ cout << 0 << endl; } } // 算法 C 的时间复杂度: 常数阶 void algorithm_C(int n){ for(int i = 0; i < 1000000; i++){ cout << 0 << endl; } } ``` - 算法 A 只打印一句话，不管参数n如何变化都只执行一次，不随着n的增大而增大，因此为常数阶 - 算法 B 中的循环会随着参数n的变化而变化，且呈上升趋势，因此为线性阶 - 算法 C 中虽然需要循环很多次，但是执行的次数不会随着参数n的变化而变化，因此为常数阶给定一个输入大小为n的函数。 ```cpp void algorithm(int n){ int a = 1; // +1 a = a + 1; // +1 a = a * 2; // +1 for(int i = 0; i < n; i++){ // +1 cout << 0 << endl; // +1 } } ``` 上述算法的操作数量为`T(n)=3+2n`。但是当n无穷大时可以忽略3这个常数，因此可以忽略不计,正确的时间复杂度应为`2n`，但是又因为这个for循环是一个整体，所以只需要看成是`n`即可。 ### 常见的时间复杂度类型 #### 1.常数阶O(1) 常数阶的操作数量与数据大小无关，不随着n的变化而变化。 ```cpp int constant(int n){ int count = 0; int size = 10000; for(int i = 0; i < size; i++) count++; return count; } ``` #### 2.线性阶O(n) 线性阶的操作数量与输入数据n以线性级别增长，通常为单个for循环 ```cpp int linear(int n){ int count = 0; for(int i = 0; i < n; i++) count++; return count; } ``` 遍历数组或链表等操作时间复杂度仍然为O(n)，其中n为数组或链表的长度 ```cpp int arrayTraversal(vector &nums){ int count = 0; for(int num : nums){ count++; } return count; } ``` #### 3.平方阶$O(n^2)$ ```cpp int quadratic(int n){ int count = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ count++; } } return count; } ``` 简单来说就是一个for循环嵌套下一个for循环。比如冒泡排序，他的时间复杂度就为$n^2$。 ```cpp int bubbleSort(vector &nums){ int count = 0; for(int i = nums.size() - 1; i > 0; i--){ for(int j = 0; j < i; j++){ if(nums[j] > nums[j + 1]){ int tmp = nums[j]; nums[j]=nums[j+1]; nums[j+1]=tmp; count += 3; } } } return count; } ``` 冒泡排序外层循环为n-1次。内层循环n-1、n-2、...、2、1次，平均为n/2次，因此时间复杂度为$O((n-1)n/2)≈O(n^2)$ #### 4.指数阶$O(2^n)$ 这个可以简单理解成细胞分裂，初始为1个细胞，第一轮分裂变成2个，第二轮变成4个，以此类推，分裂（循环）N轮就分裂出$2^n$个细胞了 ```cpp int exponential(int n){ int count = 0, base = 1; for(int i = 0; i < n; i++){ for(int j = 0; j < base; j++){ count++; } base *= 2; } return count; } ``` 与$n^2$不同的是子循环他是会随着往后的代码执行导致子循环循环次数越来越多，在实际的算法落地中，指数阶常常出现在递归函数中，如下代码所示。 ```cpp int expRecur(int n){ if(n == 1) return 1; return expRecur(n - 1) + expRecur(n - 1) + 1; } ``` #### 5.对数阶$O(log_2n)$ 与指数阶相反，对数阶反应了“每轮循环缩减一半”，设输入数据大小为n时，由于每轮缩减到一半，因此循环次数是$log_2n$，即$2^n$的反函数。 ```cpp int logarithmic(int n){ int count = 0; while(n > 1){ n = n / 2; count++; } return count; } ``` 与指数阶类似，它常常也出现在递归中。 ```cpp int logRecur(int n){ if(n <= 1) return 0; return logRecur(n / 2) + 1; } ``` #### 6.线性对数阶$O(nlog_2n)$ 线性对数阶常用于嵌套循环中。两层循环时间复杂度分别为$O(log_2n)$和O(n)。 ```cpp int linearLogRecur(int n){ if(n <= 1) return 1; int count = linearLogRecur(n / 2) + linearLogRecur(n / 2); for(int i = 0; i < n; i++){ count++; } return count; } ``` #### 7.阶乘阶O(n!) 阶层阶对于数学上的“全排列”问题。给定n个互不重复的元素，求其所有可能的排列方案，方案数量为： `n! = n * (n-1) * (n-2) * ... * 2 * 1` ```cpp int factorialRecur(int n){ if(n == 0) return 1; int count = 0; for(int i = 0; i < n; i++){ count += factorialRecur(n-1); } return count; } ``` 下面是各个时间复杂度的效率图，来源hello算法这本书 ![时间复杂度效率](/upload/images/7f3d96cc180c3190d110def8b1007edc23bd5bb0a4cf7eba7db1d93cdda7da85.png) ## 空间复杂度算法在运行中会产生三种内存类型的空间。 - 输入空间：用于存储算法输入的数据 - 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。 - 输出空间：用于存储算法的输出数据。一般情况下，空间复杂度只统计暂存空间加上输出空间。暂存空间可以进一步划分成三类。 - 暂存数据：用于保存算法运行过程中产生的各种常量、变量、对象等。 - 栈帧空间：用于保存调用函数时产生的上下文数据。 - 指令空间：用于保存编译后的程序指令，在实际统计中一般忽略不计。所以一般统计空间复杂度时只统计暂存数据、栈帧空间、输出数据三个部分的数据。 ```cpp struct Node{ int val; Node *next; Node(int x) : val(x), next(nullptr){} } int func(){ return 0; } int algorithm(int n){ const int a = 0; int b = 0; Node* node = new Node(0); int c = func(); return a + b + c; } ``` 推算空间复杂度的方法与时间复杂度类似，例如有一个数组，在不知道数据的大小情况下，就用n来代替，因为n可以说任意数，如下代码所示。 ```cpp void algorithm(int n){ int a = 0; // O(1) vector b(10000); // O(1) if (n > 10) vector nums(n); // O(n) } ``` 在递归函数中，还需要统计栈帧空间。 ```cpp int func(){ return 0; } void loop(int n){ for(int i = 0; i < n; i++){ func() } } void recur(int n){ if(n == 1) return; recur(n - 1); } ``` 函数`loop()`和`recur()`的时间复杂度都为O(n)，但是空间复杂度不一样。因为`loop()`每次循环时调用`func()`循环完毕后直接就释放了，因此空间复杂度为`O(1)`，但是`recur()`只有当n==1时递归才会往上释放内存，所以空间复杂度为`O(n)`。 ### 空间复杂度常见类型 #### 1.常数阶O(1) 常数阶中，通常与输入的n的大小无关。 ```cpp int func(){ return 0; } void constant(int n){ const int a = 0; int b = 0; vector nums(10000); ListNode node(0); for(int i = 0; i < n; i++){ int c = 0; } for(int i = 0; i < n; i++){ func(); } } ``` 在上面的代码中存在常量变量，但是他和n的大小没有直接的关联，因此空间复杂度直接就是记作O(1)。 #### 2.线性阶O(n) 线性阶常见于元素数量与n成正比的数组、链表、栈、队列等。 ```cpp void linear(int n){ vector nums(n); vector nodes; for(int i = 0; i < n; i++){ nodes.push_back(ListNode(i)); } unordered_map map; for(int i = 0; i < n; i++){ map[i] = to_string(i); } } ``` 当然这个也可以发生在递归中。 ```cpp void linearRecur(int n){ cout << "递归 n = " << n << endl; if(n == 1) return; linearRecur(n-1); } ``` 这个递归代码递归的深度为n时，就会同时存在n个未返回的`linearRecur()`函数，因此他的空间复杂度也为`O(n)` #### 3.平方阶$O(n^2)$ 平方阶通常在矩阵和图中比较常见，元素数量与n成平方关系。 ```cpp void quadratic(int n){ vector> numMatrix; for(int i = 0; i < n; i++){ vector tmp; for(int j = 0; j < n; j++){ tmp.push_back(0); } numMatrix.push_back(tmp); } } ``` 平方阶也可以通过递归实现。 ```cpp int quadraticRecur(int n){ if(n <= 0) return 0; vector nums(n); cout << "递归 n = " << n << " 中的 nums 长度 = " << nums.size() << endl; return quadraticRecur(n - 1); } ``` #### 4.指数阶$O(2^n)$ 指数阶常见于二叉树。 ```cpp TreeNode *buildTree(int n) { if(n == 0) return nullptr; TreeNode *root = new TreeNode(0); root->left = buildTree(n - 1); root->right = buildTree(n - 1); return root; } ``` #### 5.对数阶$O(log_2n)$ 对数阶常见与分治算法。例如归并排序，输入长度为n的数组，每轮递归将数组从中点处划分成两半。形成高度为$log_2n$的递归数。 # 总结时间复杂度和空间复杂度通常往往不能兼得，因此需要做出一定量的平衡，通常提升的思路就是`以空间换时间`或者`时间换空间`。具体需要那种思路这得看具体的业务场景