算法复杂度

文章目录算法复杂度前言一、数据结构前言1.1 数据结构1.2 算法二、算法效率2.1 复杂度的概念三 时间复杂度3.1 大O的渐进表示法3.2 时间复杂度示例❗总结四 空间复杂度4.1 空间复杂度示例❗总结五常见复杂度的对比六轮转数组 ⚠️算法复杂度前言本篇我们学习算法的复杂度一、数据结构前言学习数据结构之前需要具备C语言的基础结构体指针一级二级动态申请内存递归函数栈帧的创建和销毁1.1 数据结构什么是数据结构数据结构 数据的 “存放、组织、管理方式”就像整理东西随便堆在一起 无结构放抽屉、书架、收纳盒、排队 不同数据结构目的存得下、找得快、用得方便。常见主流分类线性结构一对一关系元素排成一条 “线”前后只有一个邻居数组连续空间按下标访问快链表分散空间插入删除快栈后进先出LIFO比如浏览器后退队列先进先出FIFO比如排队非线性结构一对多 / 多对多树一对多如文件夹、目录、二叉树图多对多如地图路线、社交关系网其他常用哈希表 (散列表)key-value 键值对查询极快字典、缓存常用意义算法数据结构 程序的核心同样功能用好数据结构能大幅提升程序运行效率、减少内存占用。1.2 算法算法就是教怎么用最少步骤、最少内存把问题解决得最好。常见的基础算法查找算法顺序查找二分查找最常用、最重要排序算法冒泡排序选择排序插入排序快速排序面试必考递归算法自己调用自己例如计算阶乘斐波那契数列贪心算法每一步都选当前最好的不求全局最优但快。动态规划把大问题拆成小问题存下结果避免重复算。回溯算法试错不行就退回一步再试迷宫、八皇后二、算法效率如何衡量一个算法的好坏呢这是我们需要用算法效率来衡量算法效率 算法解决问题有多快 占用多少内存主要看两个指标时间效率运行有多快时间复杂度空间效率占用多少内存空间复杂度来看一个案例超出时间限制说明算法不够好为什么超出时间限制呢关键看时间复杂度➡️下面我们学习两个指标2.1 复杂度的概念复杂度 时间复杂度(关注多 空间复杂度关注少)三 时间复杂度核心不看具体秒数只看数据量变大时运行次数怎么增长。时间复杂度 数据量 n 变大时算法执行步骤的增长趋势程序执行的时间 二进制指令运行时间可以假定时间是一样的 * 执行次数初次接触我们可能会想直接运行代码看花了几秒不就行了不行原因有 3 个电脑配置不同i9 比老旧电脑快 10 倍编程语言不同C 比 Python 快很多每次运行环境不同所以我们不算「具体时间」只算「执行了多少步」3.1 大O的渐进表示法大O符号BigOnotation是用于描述函数渐进行为的数学符号大 O 表示法O (f (n) )n 数据量比如数组有多少个元素f (n) 执行了多少步O 只看增长趋势忽略常数、小项 案例3.2 时间复杂度示例 示例1O( N ): 线性阶常用数据有多少就循环多少次特点一层循环效率中等、最常见 示例2两个变量 都分别有一层循环 对比 示例3O (1) 常数阶最快 不管数据多少永远只执行固定次数特点速度最快、最稳定 示例4strchr 是典型的线性查找算法最好情况O(1)最坏 / 平均情况O(n)❗它的效率和字符串长度成正比字符串越长查找越慢。❗总结 示例5O (n²) 平方阶最慢、尽量避免两层循环数据一多直接卡死❗典型算法冒泡排序、选择排序示例6O(log n典型应用 二分查找✨为什么可以写成O(log n❗总结这段代码的核心是 cnt * 2;每次让变量翻倍循环次数和 log₂n 成正比。时间复杂度的推导设循环次数为 x由 2^x n 推出 x log₂n所以复杂度为 O(log₂n)。大 O 表示法中对数的底数可以省略统一写成 O(log n)。这种复杂度的典型应用就是二分查找。 示例7递归算法的时间复杂度 单次递归的时间复杂度 * 递归次数四 空间复杂度空间复杂度 算法运行时 额外需要的内存空间大小的量级❗重点不算输入本身比如你给的数组、字符串只算临时变量、数组、递归栈、新开辟的空间用O(…)表示和时间复杂度规则一样4.1 空间复杂度示例 示例1 示例2递归空间 递归栈的最大深度❗总结普通变量、固定数组 → O(1)一维数组 / 链表 → O(n)二维数组 矩阵 → O(n²)递归 → 看最大深度常数系数全部忽略O(2n)O(n)五常见复杂度的对比不同的复杂度程序执行的速度不同时间 vs 空间O(1)时间快、内存小最好O(n)时间线性、内存线性O(log n)时间极快、内存很小O(n²)时间慢、内存大尽量避免六轮转数组 ⚠️现在我们学习了以上知识可以解决本文开篇的问题下面我们来一步步实现 思路一时间复杂度 O(n )2循环K次将数组所有元素向后移动⼀位代码不通过voidrotate(int*nums,intnumsSize,intk){// 外层循环k次每次把数组整体右移1位while(k--){// 1. 保存数组最后一个元素因为右移会被覆盖inttmpnums[numsSize-1];// 2. 从后往前把每个元素向后移动一位for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}// 3. 把保存的最后一个元素放到数组最前面nums[0]tmp;}} 思路二 借助第二个数组来挪动数据额外数组法时间 O (n)空间 O (n)voidrotate(int*nums,intnumsSize,intk)//nums 传入的原数组指针 numsSize 数组长度n k 向右移动步数{// 1. 处理 k 太大的情况kk%numsSize;//去掉无效旋转 比如数组长度 n7k10//向右移 10 步 向右移 3 步因为每 7 步就循环一圈//所以k 10 % 7 3//若 k0说明不用旋转直接后面复制一遍也不影响// 2. 开辟一个和原数组一样大的临时数组int*temp(int*)malloc(numsSize*sizeof(int));// 3. 把原数组元素放到临时数组的“正确位置”for(inti0;inumsSize;i){intnewPos(ik)%numsSize;// 核心公式 原数组下标 i 的元素向右移 k 步后在新数组的下标是 (ik) % ntemp[newPos]nums[i];}// 4. 把临时数组拷贝回原数组for(inti0;inumsSize;i){nums[i]temp[i];}// 5. 释放临时空间防止内存泄漏free(temp);} 思路三逆置推荐时间 O (n)空间 O (1)原理把数组分成两部分前 n-k 个元素 后 k 个元素先分别反转这两部分最后整体反转一次就得到了右移 k 位的结果 我们用数学视角看这个过程数组被分成两部分A前 n-k 个和 B后 k 个即 AB反转 A 得到 A’反转 B 得到 B’此时数组为 A’ B’反转整个数组得到 (A’ B’)’ B A正好是右移 k 位的结果这个推导用了一个关键性质(X Y) Y X当 X 和 Y 各自反转后整体反转就会交换顺序并还原内部顺序。//反转函数// 反转数组 nums 中 [left, right] 区间的元素voidreverse(int*nums,intleft,intright){// 当左指针小于右指针时一直交换两端元素while(leftright){// 交换 nums[left] 和 nums[right]inttmpnums[left];nums[left]nums[right];nums[right]tmp;// 左指针右移右指针左移向中间靠拢left;right--;}}//主函数voidrotate(int*nums,intnumsSize,intk){// 处理 k numsSize 的情况去掉无效旋转kk%numsSize;// 第一次反转前 numsSize-k 个元素reverse(nums,0,numsSize-k-1);// 第二次反转后 k 个元素reverse(nums,numsSize-k,numsSize-1);// 第三次反转整个数组reverse(nums,0,numsSize-1);}