前言在学习算法的时候我们经常会遇到一个问题为什么两个程序实现相同功能一个运行非常快一个却非常慢例如斐波那契数列long long Fib(int N) { if(N 3) return 1; return Fib(N-1)Fib(N-2); }代码非常简洁但是当数据规模变大时运行效率会快速下降。所以判断一个算法是否优秀不能只看代码量而要分析算法效率。算法效率主要从两个方面衡量时间复杂度空间复杂度一、什么是算法复杂度算法运行时会消耗1. 时间资源也就是程序运行需要多久。对应时间复杂度2. 空间资源也就是程序运行过程中需要多少额外内存。对应空间复杂度因此算法复杂度 衡量算法效率的重要指标。二、时间复杂度详解1. 时间复杂度是什么时间复杂度不是计算程序运行多少秒。因为不同机器CPU不同编译器不同环境不同运行时间都会变化。所以算法分析采用基本操作执行次数与问题规模N之间的关系例如void Func(int N) { for(int i0;iN;i) { count; } }执行次数N次因此时间复杂度 O(N)三、大O渐进表示法实际计算中我们不会关注精确次数。例如F(N)N²2N10如何表示第一步去掉常数N²2N第二步保留最高阶N²第三步去掉系数O(N²)最终时间复杂度 O(N²)四、常见时间复杂度1️⃣ O(1)常数阶int a10;执行次数不会随着N变化。2️⃣ O(N)线性阶for(int i0;iN;i) { }执行N次。3️⃣ O(N²)平方阶for(int i0;iN;i) { for(int j0;jN;j) { } }执行N*N次。4️⃣ O(logN)典型二分查找。查找过程N N/2 N/4 N/8不断缩小一半。所以O(logN)5️⃣ O(2^N)典型递归斐波那契。递归结构Fib(N) / \ Fib(N-1) Fib(N-2)递归数量快速增长2^N时间复杂度O(2^N)五、最好、平均、最坏情况很多算法输入不同执行次数不同。例如数组查找数组长度N 查找x最好情况第一次找到1次最坏情况最后找到N次平均情况约N/2次实际开发和面试中通常关注最坏情况复杂度因此数组搜索O(N)六、空间复杂度详解空间复杂度表示算法运行过程中额外占用空间。注意不是统计程序所有内存。而是额外申请的空间数量示例1O(1)int a; int b;固定变量O(1)示例2O(N)动态申请malloc(n*sizeof(int))申请N个空间O(N)Lesson2--时间复杂度空间复杂度.pdfPDF示例3递归空间递归Fac(N)调用N层产生N个栈帧空间复杂度O(N)七、算法复杂度排行榜从优秀到较差O(1) ↓ O(logN) ↓ O(N) ↓ O(NlogN) ↓ O(N²) ↓ O(2^N) ↓ O(N!)一般来说复杂度效率O(1)非常高O(logN)优秀O(N)良好O(N²)数据大时需优化O(2^N)通常不可接受八、总结本文学习了✅ 什么是算法效率✅ 时间复杂度计算方法✅ 大O渐进表示法✅ 常见复杂度分析✅ 最好、平均、最坏情况✅ 空间复杂度计算方法掌握复杂度分析是学习数组链表栈队列树图排序算法的基础。也是程序员面试中的高频考点。推荐阅读数据结构与算法学习路线复杂度分析 ↓ 线性表 ↓ 栈和队列 ↓ 树 ↓ 排序算法 ↓ 图算法 ↓ 算法设计
数据结构入门必学：时间复杂度、空间复杂度详细解析（附实例代码）
前言在学习算法的时候我们经常会遇到一个问题为什么两个程序实现相同功能一个运行非常快一个却非常慢例如斐波那契数列long long Fib(int N) { if(N 3) return 1; return Fib(N-1)Fib(N-2); }代码非常简洁但是当数据规模变大时运行效率会快速下降。所以判断一个算法是否优秀不能只看代码量而要分析算法效率。算法效率主要从两个方面衡量时间复杂度空间复杂度一、什么是算法复杂度算法运行时会消耗1. 时间资源也就是程序运行需要多久。对应时间复杂度2. 空间资源也就是程序运行过程中需要多少额外内存。对应空间复杂度因此算法复杂度 衡量算法效率的重要指标。二、时间复杂度详解1. 时间复杂度是什么时间复杂度不是计算程序运行多少秒。因为不同机器CPU不同编译器不同环境不同运行时间都会变化。所以算法分析采用基本操作执行次数与问题规模N之间的关系例如void Func(int N) { for(int i0;iN;i) { count; } }执行次数N次因此时间复杂度 O(N)三、大O渐进表示法实际计算中我们不会关注精确次数。例如F(N)N²2N10如何表示第一步去掉常数N²2N第二步保留最高阶N²第三步去掉系数O(N²)最终时间复杂度 O(N²)四、常见时间复杂度1️⃣ O(1)常数阶int a10;执行次数不会随着N变化。2️⃣ O(N)线性阶for(int i0;iN;i) { }执行N次。3️⃣ O(N²)平方阶for(int i0;iN;i) { for(int j0;jN;j) { } }执行N*N次。4️⃣ O(logN)典型二分查找。查找过程N N/2 N/4 N/8不断缩小一半。所以O(logN)5️⃣ O(2^N)典型递归斐波那契。递归结构Fib(N) / \ Fib(N-1) Fib(N-2)递归数量快速增长2^N时间复杂度O(2^N)五、最好、平均、最坏情况很多算法输入不同执行次数不同。例如数组查找数组长度N 查找x最好情况第一次找到1次最坏情况最后找到N次平均情况约N/2次实际开发和面试中通常关注最坏情况复杂度因此数组搜索O(N)六、空间复杂度详解空间复杂度表示算法运行过程中额外占用空间。注意不是统计程序所有内存。而是额外申请的空间数量示例1O(1)int a; int b;固定变量O(1)示例2O(N)动态申请malloc(n*sizeof(int))申请N个空间O(N)Lesson2--时间复杂度空间复杂度.pdfPDF示例3递归空间递归Fac(N)调用N层产生N个栈帧空间复杂度O(N)七、算法复杂度排行榜从优秀到较差O(1) ↓ O(logN) ↓ O(N) ↓ O(NlogN) ↓ O(N²) ↓ O(2^N) ↓ O(N!)一般来说复杂度效率O(1)非常高O(logN)优秀O(N)良好O(N²)数据大时需优化O(2^N)通常不可接受八、总结本文学习了✅ 什么是算法效率✅ 时间复杂度计算方法✅ 大O渐进表示法✅ 常见复杂度分析✅ 最好、平均、最坏情况✅ 空间复杂度计算方法掌握复杂度分析是学习数组链表栈队列树图排序算法的基础。也是程序员面试中的高频考点。推荐阅读数据结构与算法学习路线复杂度分析 ↓ 线性表 ↓ 栈和队列 ↓ 树 ↓ 排序算法 ↓ 图算法 ↓ 算法设计
