导图社区 GESP5级

GESP5级

算法进阶指南：从基础到高阶实战想系统掌握算法核心？本指南涵盖GESP5级必备知识点：从算法复杂度分析（多项式、指数、对数）到递归与分治（归并排序、快速排序），再到贪心策略与二分查找深入数论工具（素数筛法、唯一分解定理、辗转相除法），实现高精度运算，并熟练操作队列、栈、链表等数据结构详解时间复杂度的分类（常数、线性、对数、阶乘等），助你精准评估算法性能理论实战结合，适合有一定基础的开发者突破瓶颈！

编辑于2025-06-28 11:04:17

GESP
1算法复杂度
2排序算法
3数据结构

笨Fish

他的近期作品查看更多>>

GESP5级

社区模板帮助中心，点此进入>>

笨Fish

他的近期作品查看更多>>

相似推荐
大纲

互联网9大思维
- 33.8k
- 907
- 2.4k
- 390
MindMaster
组织架构-单商户商城webAPP 思维导图。
- 14.6k
- 3
- 184
- 10
Kacyun
域控上线
- 1.6k
- 162
- 11
- 4
jackrao
python思维导图
- 5.4k
- 525
- 242
- 7
(*^▽^*)
css
- 1.2k
- 1
- 43
- 3
A张舫
CSS
- 3.3k
- 262
- 188
- 33
journey
计算机操作系统思维导图
- 4.2k
- 333
- 203
- 18
journey
计算机组成原理
- 1.5k
- 97
- 70
- 8
journey
IMX6UL(A7)
- 512
- 40
- 5
- 0
Handler XU
考试学情分析系统
- 681
- 50
- 10
- 1
蒋龙

GESP5级

初等数论（C++）

质数

判定质数

试除法---算法复杂度：O(n)

数学概念

d 能被n整除，则 n/d 也能被n整除

例如：

n =12

因此有3种循环：

i*i <= n

i <= sqrt(n)

i <= n/i

注意：是<= ,从效率上来说，尽量不要将sqrt(n) 放入循环体，这样每次都需要调用这个函数，这个效率是最低的

方法1：

bool is_prime(int n){ if(n<2) return false; for(int i=2;i<=n/i;i++) { if(n%i==0) return false; } return true; }

方法2：

bool is_prime(int n){ if(n<2) return false; for(int i=2;i*i<n;i++) { if(n%i==0) return false; } return true; }

方法3：

bool is_prime(int n){ if(n<2) return false; int p =sqrt(n); for(int i=2;i<=p;i++) { if(n%i==0) return false; } return true; }

分解质因式

试除法

算法复杂度： O(logn~n)

数学知识：n中最多只包含一个大于根号n的质因子（优化)*

质因数分解是将一个合数分解为若干个质数相乘的形式。

例如，数字12可以分解为2×2×3，其中2和3都是质数

struct ps { long long num; int cnt; }; vector<ps> vPrimes; void divide(int n){ for(int i=2;i<=n/i;i++){ if(n%i==0) { int s=0; while(n%i==0){ -----这里去合数，例如： 2*2*2*2，直到不能被2除为止 n/=i; s++; } cout<<i<<' '<<s<<endl; struct ps tmp; tmp.num =i; tmp.cnt = s; vPrimes.push_back(tmp); } } if(n>1) cout<<n<<' '<<1<<endl; }

约数

求某数所有因数—试除法

vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; }

求约数个数——试除法分解质因式

求约数之和——试除法分解质因式

最小公倍数

A和B的最小公倍数就为A和B的乘积再除以它俩的最大公约数

int lcm( int x , int y ) { return （x*y) / gcd(x,y); }

完全平方数

完全平方数的定义，完全平方数开根号以后是一个整数，而非完全平方数开根号之后不是一个整数.

n开平方之后用int将其取整，再用取整后的值进行平方操作，

如果和原来相同，说明这是一个完全平方数，

反之则说明这不是一个完全平方数

bool ispfs(int n) { int tmp = sqrt(n); if(tmp*tmp ==n) { return true; } else { return false; } }

单链表、双链表、循环链表

链表

链表的每个元素除了存放数据还存储了下一个元素的位置信息，从而使一系列随机存放的数据串在一起，其中的数据呈线性排列。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

链表插入

插入元素：若要在元素Blue后面插入元素Green，只需要让Green指向Blue的后一个元素（Yellow），再让Blue指向Green即可；

链表删除

删除元素：若要删除元素Yellow，只需让Yellow的前一个元素（Green）直接指向Yellow的后一个元素（Red）即可；

查询元素：

若要在链表中查询数据为x的元素，需要从表头开始遍历查找（操作次数O(n)）。

双链表

循环链表

在循环单链表中，每个节点有两个部分：数据和一个指向下一个节点的指针，但是最后一个节点的指针指向头节点，而不是 null。

在循环双链表中，每个节点有三个部分：数据，一个指向下一个节点的指针和一个指向前一个节点的指针，且第一个节点的前向指针指向最后一个节点，最后一个节点的后向指针指向第一个节点。

栈

1.栈的先进后出，队列的先进先出特性

2.出入栈合法性判断

举例：入栈序列为 xxx 非法的出栈序列是？

3.前缀和后缀表达式求值，举例：求前缀表达式 + 2 * 4 5 的值。

4.链表和数组的增删改查特性。

堆栈常用函数

创建堆栈

std::stack<int> s;

压栈（Push）

将一个元素压入堆栈的顶部。

s.push(10); // 将10压入堆栈

出栈（Pop）

移除堆栈顶部的元素。需要注意的是，pop不会返回被移除的元素，如果需要访问该元素，应使用top函数。 s.pop(); // 移除顶部元素

查看栈顶元素（Top）返回堆栈顶部的元素，但不移除它。

int topElement = s.top(); // 获取顶部元素

检查堆栈是否为空（Empty）返回一个布尔值，指示堆栈是否为空。

bool isEmpty = s.empty(); // 如果堆栈为空，返回true

获取堆栈大小（Size）返回堆栈中元素的数量。

size_t stackSize = s.size(); // 获取堆栈当前大小

前缀表达式

从右往左扫描表达式，遇到数字入栈，遇到操作符，将栈顶和次顶元素出栈

假设前缀表达式为：+ * 2 3 4首先从右往左扫描表达式，遇到4,3,2, 将它们入栈，此时栈顶元素为2，次顶元素为3。扫描到 * 号，栈顶 2 和次顶 3 出栈做乘法，将结果 6 入栈。接下来继续往左扫描表达式，遇到 2 入栈，最后遇到 + 号，将栈顶 6 和次顶 4 相加，结果 10 入栈。因此，前缀表达式+ * 2 3 4的值为10。`

前缀表达式的评估

评估前缀表达式可以通过使用一个栈来实现。以下是具体的步骤：

从右到左扫描前缀表达式。

如果遇到操作数，将其压入栈中。

如果遇到运算符，弹出栈顶的两个操作数，进行相应的运算，然后将结果压入栈中。

在表达式扫描结束时，栈顶元素即为表达式的结果。

#include <iostream> #include <stack> #include <string> #include <cctype> #include <cmath> // 判断一个字符是否为运算符 bool isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'; } // 计算两个操作数的运算结果 double evaluate(double a, double b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; case '^': return pow(a, b); default: return 0; } } // 评估前缀表达式 double evaluatePrefix(const std::string& expr) { std::stack<double> stack; // 从右到左扫描前缀表达式 for (int i = expr.size() - 1; i >= 0; --i) { if (isspace(expr[i])) { continue; } // 如果是操作数（假设为单个数字字符），压入栈中 if (isdigit(expr[i])) { double num = 0; int factor = 1; while (i >= 0 && isdigit(expr[i])) { num += (expr[i] - '0') * factor; factor *= 10; --i; } stack.push(num); ++i; // 抵消内部 while loop 的 i--； } // 如果是运算符，弹出两个栈顶元素进行运算并将结果压入栈中 else if (isOperator(expr[i])) { double a = stack.top(); stack.pop(); double b = stack.top(); stack.pop(); double result = evaluate(a, b, expr[i]); stack.push(result); } } // 栈顶元素即为最终结果 return stack.top(); } int main() { std::string expr = "- + * 2 3 * 5 4 9"; // 前缀表达式 std::cout << "Given prefix expression: " << expr << std::endl; std::cout << "Evaluation result: " << evaluatePrefix(expr) << std::endl; return 0; }

后缀表达式

从左往右扫描表达式，遇到数字入栈，遇到操作符，将栈顶和次顶元素出栈

假设后缀表达式为：2 3 * 4 +从左往右扫描表达式，遇到2和 3 , 将它们入栈，遇到 * 号，将栈顶和次顶元素出栈，并计算得到 6，入栈。接下来继续往右扫描表达式，遇到 4 入栈，遇到 + 号，将栈顶和次顶元素出栈，计算得到10。因此，后缀表达式2 3 * 4 +的值为10。

后缀表达式的优点

无须括号：因为运算顺序由运算符的位置明确确定，因此不需要任何括号来改变运算的优先级。

简单的计算方式：使用栈来进行评估非常直观和简单。

后缀表达式的评估

评估后缀表达式可以通过使用一个栈来实现。以下是具体的步骤：

从左到右扫描后缀表达式。

如果遇到操作数，将其压入栈中。

如果遇到运算符，弹出栈顶的两个操作数，进行相应的运算，然后将结果压入栈中。

在表达式扫描结束时，栈顶元素即为表达式的结果。

#include <iostream> #include <stack> #include <string> #include <cctype> #include <cmath> // 判断一个字符是否为运算符 bool isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'; } // 计算两个操作数的运算结果 double evaluate(double a, double b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; case '^': return pow(a, b); default: return 0; } } // 评估后缀表达式 double evaluatePostfix(const std::string& expr) { std::stack<double> stack; // 从左到右扫描后缀表达式 for (int i = 0; i < expr.size(); ++i) { if (isspace(expr[i])) { continue; } // 如果是操作数（假设为单个数字字符），压入栈中 if (isdigit(expr[i])) { double num = 0; while (i < expr.size() && isdigit(expr[i])) { num = num * 10 + (expr[i] - '0'); ++i; } stack.push(num); --i; // 抵消内部 while loop 的 i++； } // 如果是运算符，弹出两个栈顶元素进行运算并将结果压入栈中 else if (isOperator(expr[i])) { double b = stack.top(); stack.pop(); double a = stack.top(); stack.pop(); double result = evaluate(a, b, expr[i]); stack.push(result); } } // 栈顶元素即为最终结果 return stack.top(); } int main() { std::string expr = "2 3 * 5 4 * + 9 -"; // 后缀表达式 std::cout << "Given postfix expression: " << expr << std::endl; std::cout << "Evaluation result: " << evaluatePostfix(expr) << std::endl; return 0; }

队列

1：先进先出（FIFO，First-In-First-Out）的线性表。队列只允许在后端（称为back，rear，tail）进行插入操作，在前端（称为front，head）进行删除操作

2：队列的操作入队：在队尾（称为back）进行插入或添加操作；出队：在队头（称为front）进行删除操作。

数组模拟高精度加法、减法、乘法、除法

高精度加法

实现思路：

将两个大整数以字符串的形式存储。

对两个字符串从低位到高位逐位相加。

考虑进位情况

最终得到的结果逆序存储。

#include <iostream> #include <string> #include <algorithm> // 高精度加法函数 std::string highPrecisionAdd(const std::string& num1, const std::string& num2) { std::string result; int carry = 0; // 进位 int len1 = num1.length(); int len2 = num2.length(); int i = len1 - 1, j = len2 - 1; while (i >= 0 || j >= 0 || carry) { int digit1 = i >= 0 ? num1[i--] - '0' : 0; int digit2 = j >= 0 ? num2[j--] - '0' : 0; int sum = digit1 + digit2 + carry; result.push_back(sum % 10 + '0'); carry = sum / 10; } std::reverse(result.begin(), result.end()); return result; } int main() { std::string num1, num2; std::cout << "Enter the first large number: "; std::cin >> num1; std::cout << "Enter the second large number: "; std::cin >> num2; std::string sum = highPrecisionAdd(num1, num2); std::cout << "The sum is: " << sum << std::endl; return 0; }

高精度减法

实现思路

将两个大整数以字符串的形式存储。

确保第一个数大于或等于第二个数（如果不是则交换，并标记结果为负）。

对两个字符串从低位到高位逐位相减。

考虑借位情况。

最终得到的结果可能需要去除前导零。

#include <iostream> #include <string> #include <algorithm> // 判断 num1 是否大于等于 num2 bool isGreaterOrEqual(const std::string& num1, const std::string& num2) { if (num1.length() != num2.length()) return num1.length() > num2.length(); return num1 >= num2; } // 高精度减法函数 std::string highPrecisionSubtract(std::string num1, std::string num2) { // 确保 num1 >= num2，否则交换，并标记符号 bool isNegative = false; if (!isGreaterOrEqual(num1, num2)) { std::swap(num1, num2); isNegative = true; } std::string result; int len1 = num1.length(); int len2 = num2.length(); int i = len1 - 1, j = len2 - 1; int borrow = 0; while (i >= 0 || j >= 0) { int digit1 = i >= 0 ? num1[i--] - '0' : 0; int digit2 = j >= 0 ? num2[j--] - '0' : 0; int diff = digit1 - digit2 - borrow; if (diff < 0) { diff += 10; borrow = 1; } else { borrow = 0; } result.push_back(diff + '0'); } // 去除前导零 while (result.length() > 1 && result.back() == '0') result.pop_back(); if (isNegative) result.push_back('-'); std::reverse(result.begin(), result.end()); return result; }

高精度乘法

将两个大整数以字符串的形式存储。

将每一位的乘积累加到结果数组。

处理进位。

最终将数组中的结果转换为字符串，并去除前导零。

#include <iostream> #include <string> #include <vector> #include <algorithm> // 高精度乘法函数 std::string highPrecisionMultiply(const std::string& num1, const std::string& num2) { int len1 = num1.length(); int len2 = num2.length(); std::vector<int> result(len1 + len2, 0); // 逐位相乘并累加到结果数组 for (int i = len1 - 1; i >= 0; --i) { for (int j = len2 - 1; j >= 0; --j) { int mul = (num1[i] - '0') * (num2[j] - '0'); int p1 = i + j, p2 = i + j + 1; int sum = mul + result[p2]; result[p1] += sum / 10; result[p2] = sum % 10; } } // 转换结果数组为字符串 std::string resultStr; for (int num : result) { if (!(resultStr.empty() && num == 0)) { // 跳过前导零 resultStr.push_back(num + '0'); } } return resultStr.empty() ? "0" : resultStr; } int main() { std::string num1, num2; std::cout << "Enter the first large number: "; std::cin >> num1; std::cout << "Enter the second large number: "; std::cin >> num2; std::string product = highPrecisionMultiply(num1, num2); std::cout << "The product is: " << product << std::endl; return 0; }

高进度除法

实现思路

长除法逐位计算：

从被除数最高位开始逐位处理。

每次试探性的将部分的被除数除以除数，得到商的某一位。

使用减法更新被除数的对应部分。

处理结果前导零。

#include <iostream> #include <string> #include <algorithm> // 高精度减法，用于除法过程中的试探减法 std::string subtract(const std::string& num1, const std::string& num2) { std::string result; int len1 = num1.length(); int len2 = num2.length(); int borrow = 0; for (int i = 0; i < len1; ++i) { int digit1 = num1[len1 - 1 - i] - '0'; int digit2 = i < len2 ? num2[len2 - 1 - i] - '0' : 0; int diff = digit1 - digit2 - borrow; if (diff < 0) { diff += 10; borrow = 1; } else { borrow = 0; } result.push_back(diff + '0'); } // 去除前导零 while (result.length() > 1 && result.back() == '0') result.pop_back(); std::reverse(result.begin(), result.end()); return result; } // 高精度除法函数，返回商和余数 std::pair<std::string, std::string> highPrecisionDivide(const std::string& dividend, const std::string& divisor) { if (divisor == "0") throw std::invalid_argument("Divisor cannot be zero."); std::string quotient; std::string remainder; for (char digit : dividend) { remainder += digit; int count = 0; while (remainder.length() > 1 && remainder[0] == '0') remainder.erase(0, 1); while (remainder.length() > divisor.length() || (remainder.length() == divisor.length() && remainder >= divisor)) { remainder = subtract(remainder, divisor); ++count; } quotient.push_back(count + '0'); } while (quotient.length() > 1 && quotient[0] == '0') quotient.erase(0, 1); return {quotient, remainder}; } int main() { std::string num1, num2; std::cout << "Enter the dividend large number: "; std::cin >> num1; std::cout << "Enter the divisor large number: "; std::cin >> num2; try { auto [quotient, remainder] = highPrecisionDivide(num1, num2); std::cout << "The quotient is: " << quotient << std::endl; std::cout << "The remainder is: " << remainder << std::endl; } catch (const std::invalid_argument& e) { std::cerr << e.what() << std::endl; } return 0; }

辗转相除法（也称欧几里得算法）

最大公约数——欧几里得算法

int gcd(int a, int b)

return b ? gcd(b, a % b) : a;

非递归算法：辗转除余法

int gcd( int x , int y){

int max,min,temp;

max = x > y ? x : y ;

min = x < y ? x : y ;

while( max % min ){

temp = max % min;

max = min;

min = temp;

return min;

素数表的埃氏筛法和线性筛法

素数筛法，是一种快速“筛”出2~n之间所有素数的方法。

埃式筛法

素数筛法，是一种快速“筛”出2~n之间所有素数的方法。时间复杂度 o(nlognlogn)

过程写成代码就是：

bool isnp[MAXN] = {0x0}; void init(int n){ for (int i = 2; i * i <= n; i++) if (!isnp[i]) for (int j = i * i; j <= n; j += i) isnp[j] = 1; }

线性筛法

埃式筛法筛的过程中我们会重复筛到同一个数，

线性筛法的核心步骤，就是避免将一个合数被标记多次，以此达到O(n)的时间复杂度。

体现在代码里面，就是：if (i % primes[j] == 0) break;。

bool st[N]; int prime[N]; int cnt; int is_prime(int n) { for(int i=2;i<=n;i++) { if(!st[i]) prime[cnt++]=i; for(int j=0;prime[j]<=n/i;j++) { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } }

唯一分解定理

唯一分解定理（Fundamental Theorem of Arithmetic），也称为算术基本定理，是数论中的一个重要定理。它指出：

每一个大于1的正整数都可以唯一地表示为若干个质数的乘积（质因数分解），质数的顺序不同则不计。

举例说明：

30 = 2 × 3 × 5

60 = 2 × 2 × 3 × 5

84 = 2 × 2 × 3 × 7

#include <iostream> #include <vector> // 获取质因数分解 std::vector<int> primeFactorization(int n) { std::vector<int> factors; for (int i = 2; i * i <= n; ++i) { while (n % i == 0) { factors.push_back(i); n /= i; } } if (n > 1) { factors.push_back(n); } return factors; } int main() { int number; std::cout << "Enter a number to decompose into prime factors: "; std::cin >> number; std::vector<int> factors = primeFactorization(number); std::cout << "Prime factors of " << number << " are: "; for (int factor : factors) { std::cout << factor << " "; } std::cout << std::endl; return 0; }

二分查找/二分答案（也称二分枚举法）

二分查找（Binary Search）是一种高效的查找算法，适用于在已排序的数组或列表中查找指定元素。

其基本思想是通过将查找范围逐步减半，从而快速定位目标元素的位置。

工作原理：

初始范围：确定查找的初始范围，即数组的起始索引和结束索引。

计算中间点：计算中间点的索引。

比较中间点元素：将中间点的元素与目标元素进行比较。

如果中间点的元素等于目标元素，则查找成功，返回中间点索引。

如果中间点的元素小于目标元素，则说明目标元素在中间点右侧，将查找范围缩小为右半部分。

如果中间点的元素大于目标元素，则说明目标元素在中间点左侧，将查找范围缩小为左半部分。

重复步骤2和3：继续在缩小后的范围内查找，直到找到目标元素或范围为空。

#include <iostream> #include <vector> int binarySearch(const std::vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // 未找到 } int main() { std::vector<int> arr = {2, 3, 4, 10, 40}; int target = 10; int result = binarySearch(arr, target); if (result == -1) { std::cout << "Element not present in array" << std::endl; } else { std::cout << "Element found at index " << result << std::endl; } return 0; }

贪心算法

分治算法（归并排序和快速排序）

归并排序

归并排序（Merge Sort）是一种经典的排序算法，属于分治法（Divide and Conquer）策略。

它将一个大的排序问题分解成若干个小的子问题，解决这些子问题后，再将结果合并，从而得到最终的排序结果。

归并排序的基本思想：

分解（Divide）：将未排序的数组分成两个大致相等的子数组。

解决（Conquer）：递归地对子数组进行排序。

合并（Combine）：将两个有序的子数组合并成一个有序的数组

归并排序的递归实现步骤：

递归基准：如果数组的长度为1（即只有一个元素），则认为数组已经是有序的，直接返回。

递归分解：将数组分成左右两个子数组，继续对这两个子数组进行归并排序。

合并步骤：将两个已经排序好的子数组合并成一个有序数组。

#include <iostream> #include <vector> // 合并两个有序子数组 void merge(std::vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; // 左子数组长度 int n2 = right - mid; // 右子数组长度 // 创建两个临时数组 std::vector<int> L(n1); std::vector<int> R(n2); // 拷贝数据到临时数组 L 和 R for (int i = 0; i < n1; ++i) L[i] = arr[left + i]; for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j]; // 合并两个临时数组到原数组 int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; ++i; } else { arr[k] = R[j]; ++j; } ++k; } // 复制剩余的元素 while (i < n1) { arr[k] = L[i]; ++i; ++k; } while (j < n2) { arr[k] = R[j]; ++j; ++k; } } // 归并排序 void mergeSort(std::vector<int>& arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // 递归归并排序左右子数组 mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // 合并已排序的子数组 merge(arr, left, mid, right); } } int main() { std::vector<int> arr = {12, 11, 13, 5, 6, 7}; std::cout << "Given array: "; for (int x : arr) std::cout << x << " "; std::cout << std::endl; mergeSort(arr, 0, arr.size() - 1); std::cout << "Sorted array: "; for (int x : arr) std::cout << x << " "; std::cout << std::endl; return 0; }

快速排序

快速排序（Quick Sort）是一种非常高效的排序算法，也是归纳排序和基数排序之外的另一种“分治”策略的典型例子。它通过递归地将数据集分成较小的子数据集，从而将问题简化，逐步将整个数据集排序。

快速排序的基本思想：

选择主元（Pivot）：从数组中选择一个元素作为主元，这个元素通常称为“基准”。

分区（Partition）：重排数组，使得所有小于主元的元素都位于它的左侧，所有大于主元的元素都位于它的右侧。主元位于其最终的位置上。

递归排序：递归地对左右子数组进行快速排序。

关键步骤解释：

选择主元：主元的选择可以用多种方式，如选择第一个元素、最后一个元素、随机选择、或者选择中间元素。在简单实现中，常用较容易实现的选择方式。

分区过程：扫描数组，将小于主元的元素移到左边，大于主元的元素移到右边。

递归调用：对分区后的子数组继续进行同样的排序算法，直到每个部分已是有序。

#include <iostream> #include <vector> // 分区函数，将选定的主元放在正确位置，并使得左侧元素小于主元，右侧元素大于主元 int partition(std::vector<int>& arr, int low, int high) { int pivot = arr[high], i = low - 1; for (int j = low; j <= high - 1; ++j) { if (arr[j] < pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return (i + 1); } // 快速排序主函数 void quickSort(std::vector<int>& arr, int low, int high) { if (low < high) { // pi 是分区点 int pi = partition(arr, low, high); // 递归排序左侧和右侧的子数组 quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { std::vector<int> arr = {10, 7, 8, 9, 1, 5}; std::cout << "Given array: "; for (int x : arr) std::cout << x << " "; std::cout << std::endl; quickSort(arr, 0, arr.size() - 1); std::cout << "Sorted array: "; for (int x : arr) std::cout << x << " "; std::cout << std::endl; return 0; }

递归

算法复杂度的估算（含多项式、指数、对数复杂度）

在计算机科学中，算法复杂度用于衡量算法在最坏和平均情况下所需的资源（如时间和空间）。主要有以下几种常见的复杂度类型：

常数时间复杂度

O(1)：

不随输入规模的变化而变化。例如，数组访问元素操作。

线性时间复杂度

O(n)：

随着输入规模呈线性增长。例如，线性搜索。

对数时间复杂度

O(logn)：

随着输入规模的对数增长。例如，二分查找。

// 示例：二分查找 int binarySearch(int arr[], int low, int high, int x) { while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == x) return mid; if (arr[mid] < x) low = mid + 1; else high = mid - 1; } return -1; }

线性对数时间复杂度

O(nlogn)：

混合线性和对数增长。例如，归并排序和快速排序。

// 示例：快速排序 void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }

二次时间复杂度

O(n**2）：

矩阵乘法或嵌套双重循环。例如，选择排序和插入排序。

指数时间复杂度

// 示例：选择排序 void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j; std::swap(arr[minIdx], arr[i]); } }

O(2**n)：

常见于递归算法如解决子集问题或汉诺塔问题。例如，通过对所有子集进行穷举搜索。

// 示例：计算斐波那契数列 int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

随着输入规模呈指数增长。例如，解决所有子集问题的穷举搜索。

多项式时间复杂度

O(n**k)（其中 k 是常数）：

多轮循环操作。例如，求矩阵的某些属性。

常见的多层嵌套循环。

// 示例：矩阵乘法 void matrixMultiply(int A[][N], int B[][N], int C[][N], int N) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i][j] = 0; for (int k = 0; k < N; k++) { C[i][j] += A[i][k] * B[k][j]; } } } }

阶乘时间复杂度

O(n!)：

正常情况下，所有排列或组合。例如，旅行商问题的暴力求解。

常见于排列组合问题。

// 示例：旅行商问题的暴力求解 void tsp(int graph[][V], bool v[], int currPos, int n, int count, int cost, int& ans) { if (count == n && graph[currPos][0]) { ans = std::min(ans, cost + graph[currPos][0]); return; } for (int i = 0; i < n; i++) { if (!v[i] && graph[currPos][i]) { v[i] = true; tsp(graph, v, i, n, count + 1, cost + graph[currPos][i], ans); v[i] = false; } } }