你是不是刚学算法时一看到O(n)、O(logn)、O(n²)就头大不知道怎么算、为什么这么算、面试又怎么考这篇博客从零开始、全程图文 代码 例子把时间 / 空间复杂度讲得明明白白完全适合零基础初学者看完直接会做题、会面试。前言为什么要学复杂度我们写代码不只是 “能跑出来” 就行还要跑得快、占内存少。比如同样算斐波那契数列文章末尾有详细代码递归写法简洁但巨慢迭代写法代码长一点但飞快怎么客观衡量快慢与占用内存答案就是时间复杂度 空间复杂度。时间复杂度看算法跑多快执行次数空间复杂度看算法占多少额外内存临时变量这是数据结构与算法第一课也是笔试面试必考点。一、先搞懂大 O 渐进表示法核心我们不算精确运行时间只看趋势用大 O 符号表示。推导大 O 3 条黄金法则背会只保留最高阶项低阶项忽略比如 N²2N10 → 只看 N²常数系数直接删掉比如 3N → O (N)5logN → O (logN)常数一律变成 O (1)不管 10、100、1000 次都是 O (1)一句话总结只看增长最快的那一项去掉系数就是复杂度至于为什么这么考虑因为计算机处理数据飞快而庞大我们只需要关注最能够影响数据的地方比如N²2N10当N越来越大时 N²的增长速度远大于2N可以忽略掉2N跟无穷相似。当然计算机的计算速度和数据处理量不可能是无穷的。二、时间复杂度算法到底跑多快2.1 什么是时间复杂度时间复杂度 算法中基本操作的执行次数不是毫秒、不是秒是执行了多少次。我们只看最坏情况面试 / 考试统一标准。比如在数组里找数最好第 1 个就找到 → 1 次最坏找完整个数组 → N 次统一按最坏算O (N)2.2 8 个经典例子逐行带你算我把文档里所有例题全部拆开讲保证初学者一看就会。例 1双层循环c运行void Func1(int N) { int count 0; // 第一层 N 次 for (int i 0; i N; i) { // 第二层 N 次 for (int j 0; j N; j) { count; // 执行 N*N N² 次 } } // 执行 2*N 次 for (int k 0; k 2*N; k) { count; } // 执行 10 次 int M 10; while (M--) count; }总次数N² 2N 10按规则保留最高阶O(N²)例 2单层循环c运行void Func2(int N) { for (int k 0; k 2*N; k) count; int M 10; while (M--) count; }次数2N 10→ 去系数 →O(N)例 3固定次数c运行void Func4(int N) { // 只跑 100 次 for (int k 0; k 100; k) count; }常数 →O(1)例 4strchr 字符串查找在字符串里找一个字符最坏要遍历整个串 →O(N)例 5冒泡排序 BubbleSortc运行void BubbleSort(int a[], int n) { for (int end n; end 0; end--) { int exchange 0; for (int i 1; i end; i) { if (a[i-1] a[i]) { swap(a[i-1], a[i]); exchange 1; } } if (exchange 0) break; } }最坏情况每次都要交换次数 ≈ N (N-1) … 1 N(N1)/2→O(N²)例 6二分查找 BinarySearch重点c运行int BinarySearch(int a[], int n, int x) { int begin 0, end n-1; while (begin end) { int mid begin (end-begin)/2; if (a[mid] x) return mid; else if (a[mid] x) begin mid1; else end mid-1; } return -1; }每次范围砍半n → n/2 → n/4 → … → 1执行次数 log₂N复杂度O(logN)注意算法里 logN 默认以 2 为底不写底数。例 7阶乘递归c运行long long Fac(int N) { if (N 0) return 1; return Fac(N-1) * N; }递归 N 次 →O(N)例 8斐波那契递归巨慢c运行long long Fib(int N) { if (N 3) return 1; return Fib(N-1) Fib(N-2); }每层递归分裂成 2 个呈指数增长次数 ≈2^N复杂度O(2ⁿ)爆炸级慢三、空间复杂度占多少额外内存3.1 概念空间复杂度 算法运行时临时开辟的额外空间不算输入、不算输出只看临时变量 / 动态开辟 / 递归栈。规则和时间复杂度一样也用大 O。3.2 3 个经典例题例 1冒泡排序c运行void BubbleSort(...) { int exchange 0; // 常数个变量 }只开了常数个变量→O(1)例 2斐波那契数组迭代c运行long long* Fib(int n) { // malloc 开辟 n1 个空间 long long* arr (long long*)malloc( (n1)*sizeof(long long) ); arr[0] 0; arr[1] 1; for(int i2; in; i) arr[i] arr[i-1]arr[i-2]; return arr; }动态开了n 个空间→O(N)例 3阶乘递归c运行long long Fac(int N) { if(N0) return 1; return Fac(N-1)*N; }递归调用 N 次开辟N 个栈帧→O(N)四、常见复杂度速查表背会从快到慢排序O(1)常数阶最快O(logN)对数阶O(N)线性阶O(NlogN)O(N²)平方阶O(2ⁿ)指数阶巨慢尽量避免五、笔试 / 面试常考直接背冒泡 / 插入 / 选择排序O(N²)快速 / 归并 / 堆排序O(NlogN)二分查找O(logN)哈希表查找O(1)斐波那契递归O(2ⁿ)斐波那契迭代O(N)六、初学者最容易犯的 5 个错误把 logN 当成 lnN/lgN算法里一律默认以 2 为底递归空间复杂度不会算看递归深度深度多少就是多少算复杂度带常数3N → O(N)100N² → O(N²)看最好情况考试 / 面试统一看最坏以为代码短就复杂度低斐波那契递归最短但最慢七、总结一张图学会时间复杂度看执行次数取最坏用大 O空间复杂度看额外开辟空间三大规则保最高阶、去系数、常数变 O (1)常见复杂度O (1) O (logN) O (N) O (NlogN) O (N²) O (2ⁿ)八、课后小练习答案在文末单层 for 循环 N 次 → 二分查找 → 两层嵌套 for 循环 → 斐波那契递归 → 只开 3 个临时变量 → 答案O(N) 2. O(logN) 3. O(N²) 4. O(2ⁿ) 5. O(1)两道复杂度脸没洗的程序设计题目链接1.消失的数字OJ链接https://leetcode-cn.com/problems/missing-number-lcci/2.旋转数组OJ链接https://leetcode-cn.com/problems/rotate-array/
【数据结构】算法时间复杂度与空间复杂度
发布时间：2026/5/30 3:55:17
你是不是刚学算法时一看到O(n)、O(logn)、O(n²)就头大不知道怎么算、为什么这么算、面试又怎么考这篇博客从零开始、全程图文 代码 例子把时间 / 空间复杂度讲得明明白白完全适合零基础初学者看完直接会做题、会面试。前言为什么要学复杂度我们写代码不只是 “能跑出来” 就行还要跑得快、占内存少。比如同样算斐波那契数列文章末尾有详细代码递归写法简洁但巨慢迭代写法代码长一点但飞快怎么客观衡量快慢与占用内存答案就是时间复杂度 空间复杂度。时间复杂度看算法跑多快执行次数空间复杂度看算法占多少额外内存临时变量这是数据结构与算法第一课也是笔试面试必考点。一、先搞懂大 O 渐进表示法核心我们不算精确运行时间只看趋势用大 O 符号表示。推导大 O 3 条黄金法则背会只保留最高阶项低阶项忽略比如 N²2N10 → 只看 N²常数系数直接删掉比如 3N → O (N)5logN → O (logN)常数一律变成 O (1)不管 10、100、1000 次都是 O (1)一句话总结只看增长最快的那一项去掉系数就是复杂度至于为什么这么考虑因为计算机处理数据飞快而庞大我们只需要关注最能够影响数据的地方比如N²2N10当N越来越大时 N²的增长速度远大于2N可以忽略掉2N跟无穷相似。当然计算机的计算速度和数据处理量不可能是无穷的。二、时间复杂度算法到底跑多快2.1 什么是时间复杂度时间复杂度 算法中基本操作的执行次数不是毫秒、不是秒是执行了多少次。我们只看最坏情况面试 / 考试统一标准。比如在数组里找数最好第 1 个就找到 → 1 次最坏找完整个数组 → N 次统一按最坏算O (N)2.2 8 个经典例子逐行带你算我把文档里所有例题全部拆开讲保证初学者一看就会。例 1双层循环c运行void Func1(int N) { int count 0; // 第一层 N 次 for (int i 0; i N; i) { // 第二层 N 次 for (int j 0; j N; j) { count; // 执行 N*N N² 次 } } // 执行 2*N 次 for (int k 0; k 2*N; k) { count; } // 执行 10 次 int M 10; while (M--) count; }总次数N² 2N 10按规则保留最高阶O(N²)例 2单层循环c运行void Func2(int N) { for (int k 0; k 2*N; k) count; int M 10; while (M--) count; }次数2N 10→ 去系数 →O(N)例 3固定次数c运行void Func4(int N) { // 只跑 100 次 for (int k 0; k 100; k) count; }常数 →O(1)例 4strchr 字符串查找在字符串里找一个字符最坏要遍历整个串 →O(N)例 5冒泡排序 BubbleSortc运行void BubbleSort(int a[], int n) { for (int end n; end 0; end--) { int exchange 0; for (int i 1; i end; i) { if (a[i-1] a[i]) { swap(a[i-1], a[i]); exchange 1; } } if (exchange 0) break; } }最坏情况每次都要交换次数 ≈ N (N-1) … 1 N(N1)/2→O(N²)例 6二分查找 BinarySearch重点c运行int BinarySearch(int a[], int n, int x) { int begin 0, end n-1; while (begin end) { int mid begin (end-begin)/2; if (a[mid] x) return mid; else if (a[mid] x) begin mid1; else end mid-1; } return -1; }每次范围砍半n → n/2 → n/4 → … → 1执行次数 log₂N复杂度O(logN)注意算法里 logN 默认以 2 为底不写底数。例 7阶乘递归c运行long long Fac(int N) { if (N 0) return 1; return Fac(N-1) * N; }递归 N 次 →O(N)例 8斐波那契递归巨慢c运行long long Fib(int N) { if (N 3) return 1; return Fib(N-1) Fib(N-2); }每层递归分裂成 2 个呈指数增长次数 ≈2^N复杂度O(2ⁿ)爆炸级慢三、空间复杂度占多少额外内存3.1 概念空间复杂度 算法运行时临时开辟的额外空间不算输入、不算输出只看临时变量 / 动态开辟 / 递归栈。规则和时间复杂度一样也用大 O。3.2 3 个经典例题例 1冒泡排序c运行void BubbleSort(...) { int exchange 0; // 常数个变量 }只开了常数个变量→O(1)例 2斐波那契数组迭代c运行long long* Fib(int n) { // malloc 开辟 n1 个空间 long long* arr (long long*)malloc( (n1)*sizeof(long long) ); arr[0] 0; arr[1] 1; for(int i2; in; i) arr[i] arr[i-1]arr[i-2]; return arr; }动态开了n 个空间→O(N)例 3阶乘递归c运行long long Fac(int N) { if(N0) return 1; return Fac(N-1)*N; }递归调用 N 次开辟N 个栈帧→O(N)四、常见复杂度速查表背会从快到慢排序O(1)常数阶最快O(logN)对数阶O(N)线性阶O(NlogN)O(N²)平方阶O(2ⁿ)指数阶巨慢尽量避免五、笔试 / 面试常考直接背冒泡 / 插入 / 选择排序O(N²)快速 / 归并 / 堆排序O(NlogN)二分查找O(logN)哈希表查找O(1)斐波那契递归O(2ⁿ)斐波那契迭代O(N)六、初学者最容易犯的 5 个错误把 logN 当成 lnN/lgN算法里一律默认以 2 为底递归空间复杂度不会算看递归深度深度多少就是多少算复杂度带常数3N → O(N)100N² → O(N²)看最好情况考试 / 面试统一看最坏以为代码短就复杂度低斐波那契递归最短但最慢七、总结一张图学会时间复杂度看执行次数取最坏用大 O空间复杂度看额外开辟空间三大规则保最高阶、去系数、常数变 O (1)常见复杂度O (1) O (logN) O (N) O (NlogN) O (N²) O (2ⁿ)八、课后小练习答案在文末单层 for 循环 N 次 → 二分查找 → 两层嵌套 for 循环 → 斐波那契递归 → 只开 3 个临时变量 → 答案O(N) 2. O(logN) 3. O(N²) 4. O(2ⁿ) 5. O(1)两道复杂度脸没洗的程序设计题目链接1.消失的数字OJ链接https://leetcode-cn.com/problems/missing-number-lcci/2.旋转数组OJ链接https://leetcode-cn.com/problems/rotate-array/
