算法复杂度的估算（含多项式、指数、对数复杂度）-野牛程序员讲少儿编程
作者：野牛程序员：2025-05-09 18:58:11算法阅读 1991
算法复杂度的估算（含多项式、指数、对数复杂度）-野牛程序员讲少儿编程
📘 什么是算法复杂度？
算法复杂度，是用来描述算法执行效率的工具。通常分为两类：
| 类型 | 含义 |
|---|---|
| 时间复杂度 | 算法运行所需的「操作步骤数量」 |
| 空间复杂度 | 算法运行所占用的「内存大小」 |
其中，时间复杂度最常见，表示当输入数据规模 n 增大时，程序运行时间变化趋势。
📏 常见复杂度等级（从快到慢）
| 复杂度表达式 | 名称 | 举例 |
|---|---|---|
O(1) | 常数时间 | 判断奇偶：x % 2 == 0 |
O(log n) | 对数时间 | 折半查找（二分查找） |
O(n) | 线性时间 | 遍历数组一遍 |
O(n log n) | 线性对数时间 | 快速排序、归并排序 |
O(n²) | 平方时间 | 两层循环（如冒泡排序） |
O(2^n) | 指数时间 | 递归搜索子集（暴力搜索） |
O(n!) | 阶乘时间（最慢） | 全排列枚举 |
🍬 通俗理解
假设有 n 个糖果，要从中找出最甜的一颗：
O(1)：老师直接告诉答案（最省事）
O(n)：一个个尝过去（遍历）
O(log n)：先猜一半，看在哪边继续猜（折半）
O(n²)：每颗都跟其他糖比甜度（成对比较）
O(2ⁿ)：所有可能的吃法都试一遍（组合爆炸）
📌 示例代码讲解（含主函数与注释）
1️⃣ O(n) — 线性复杂度
#include <iostream>
using namespace std;
// 功能：输出前 n 个数字的和
int linearSum(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) // 循环 n 次
sum += i;
return sum;
}
int main() {
int n = 100000;
cout << "前 " << n << " 个数之和是：" << linearSum(n) << endl;
return 0;
}2️⃣ O(log n) — 对数复杂度（二分查找）
#include <iostream>
using namespace std;
// 功能：在升序数组中查找目标值 target
bool binarySearch(int a[], int n, int target) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == target)
return true;
else if (a[mid] < target)
l = mid + 1;
else
r = mid - 1;
}
return false;
}
int main() {
int a[] = {1, 3, 5, 7, 9, 11, 13};
int n = 7, target = 9;
if (binarySearch(a, n, target))
cout << "找到目标值！" << endl;
else
cout << "目标值不存在" << endl;
return 0;
}3️⃣ O(n²) — 冒泡排序
#include <iostream>
using namespace std;
// 功能：对数组进行冒泡排序
void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) // 外层 n-1 次
for (int j = 0; j < n - 1 - i; j++) // 内层也约为 n 次
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
}
int main() {
int a[] = {5, 2, 9, 1, 3};
int n = 5;
bubbleSort(a, n);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}🚀 小学生能懂的记忆口诀
| 等级 | 口诀（比喻） |
|---|---|
O(1) | 秒回消息 |
O(log n) | 一猜一半找目标（猜数游戏） |
O(n) | 一个个过（排队查身高） |
O(n²) | 人人比（班级同学互相问卷） |
O(2ⁿ) | 所有组合都试（翻牌、配对游戏） |
野牛程序员教少儿编程与信息学奥赛-微信|电话：15892516892
