东莞南海网站制作,佛山建筑公司排名,北海做网站的网络公司,重庆建站网站建设平台文章目录 前言 一、算法的复杂度 二、时间复杂度 三、空间复杂度 四、例题 1、例1#xff1a;冒泡排序 2、例2#xff1a; 3、例3#xff1a; 4、例4: 二分查找 5、例5: 阶乘 6、例6: 斐波那契 五、常见算法复杂度 总结 前言
路漫漫其修远兮#xff0c;吾将上下而求索冒泡排序 2、例2 3、例3 4、例4: 二分查找 5、例5: 阶乘 6、例6: 斐波那契 五、常见算法复杂度 总结 前言
路漫漫其修远兮吾将上下而求索 一、算法的复杂度
当我们编写了一个 算法之后如何衡量这个算法到底是好还是坏呢
算法在运行的过程中最重要的指标是此算法快不快以及其在运行的过程之中会消耗多少空间即时间复杂度与空间复杂度 时间复杂度衡量一个算法运行的运行快慢 空间复杂度衡量一个算法运行时所需要的额外空间 注在早期计算机的发展中由于计算机的存储容量小所以比较关注空间复杂度但是随着计算机行业的快速发展(摩尔定律每18个月计算机的硬件便会翻一倍)内存越来越大并且越来越便宜于是现在就不那么关注空间复杂度了
二、时间复杂度
算法的时间复杂度是一个函数它定量地描述了该算法的运行时间(该算法执行所消耗的时间)理论来说时间复杂度是不可能算出来的只有当此程序在机器上跑起来的时候才可以知道此算法运行的时间
注此处所述的函数并不是在C语言中的那个函数而是在数学之中的函数表达式
时间复杂度为什么不是用来计算该代码运行了多少秒呢
因为并没有一个准确的方式去计算一个算法运行了多少秒相同的算法在不同的机器上是有差异的即一个算法的执行速度受环境的影响
那么时间复杂度究竟计算的是什么呢
计算的是一个算法之中基本操作(代码)的执行次数哪个算法的基本操作的执行次数少那么该算法便会更快
一个算法花费的时间与其语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度找到某条基本语句与问题规模N之间的数学表达式并且在计算的时候也不需要计算该算法精确的执行次数只需要大概的执行次数便可以了那么这里便会使用到大O的渐近表示法
何为大O的渐进表示法
大O符号Big O notation: 用于描述函数渐进行为的数学符号 推导大O阶方法 用常数1取代运行时间中的所有加法常数在修改后的运行次数函数中只保留最高阶项如果最高阶项存在并且不是1则去除与这个项目相乘的常数(让最高项的系数为1) 最后所得到的结果便是大O阶 例子代码如下
void Func1(int N)
{int i 0;int j 0;int k 0;int count 0;for (i 0; i N; i){for(j 0; j N; j){count;}}for(k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
} 倘若要准确地计算上述代码的执行次数 N^2 2*N M (其中M为10是一个常数)
根据推导大O阶规则则会得到该算法的时间复杂度为O(N^2) 从上例我们可以得知大O的渐进表示法去掉了那些对结果影响不大的项保留了对结果影响最大的项(可以采用数学极限的思想)
计算时间复杂度的技巧可以大致计算”精确“的然后再在此基础上利用推导大O阶规则
另外在有些算法中时间复杂度存在最好、平均、最坏的情况 最好的情况任意输入规模的最小运行次数 平均的情况任意输入规模的期望运行次数 最坏的情况任意输入规模的最大运行次数 我们在计算一个算法的时间复杂度的时候一般关注的是其最坏的情况
三、空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时额外占用存储空间大小的量度
空间复杂度并不是精确计算这个程序占用了多少byte 的空间而是采用大O渐进表达式的方式来计算在运行过程中额外运用了多少空间
注函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器的信息等)在编译期间便已经确定好了因此空间复杂度主要通过函数在运行的时候显式申请的额外空间来确定的
换句话说空间复杂度的计算的是在运行过程中额外占用存储空间的变量个数倘若在运行的过程中建立栈帧这也是要算入的并且遵循推导大O阶的规则
四、例题
1、例1冒泡排序 分析 分析时间、空间复杂度的核心是梳理清楚整个代码的逻辑 显然冒泡排序的逻辑为整个冒泡排序会有两个循环一个控制循环的趟数一个控制一趟排序之中相邻两元素所要比较的次数并且每次冒完一趟均会确定好一个元素的最终位置故而每冒完一趟下一趟冒泡均会减少一次比较 如此大致看起来冒泡排序的基本代码执行次数为一个等差数列之和而复杂度采取的是大O渐进表达式的估算法即相加的常数项为1只保留最高项并且最高项的系数为1显然其时间复杂度变为O(N^2);
而整个冒泡排序的过程都只是在一定大小的数组进行的并没有使用额外的空间所以其空间复杂度为O(1)
2、例2 分析 注大O渐进表达式用的未知数用的是N有时也可以是M、K等字母 为什么此处的时间复杂度为O(NM)
因为在此处N 与 M 均为未知数并不知道谁大谁小按照推导大O阶的方式于是乎便得到了O(NM);
倘若此处有N 与 M 的大小关系其时间复杂度便会不同 而对于此算法的空间复杂度整个算法的执行依靠的是几个变量并没有使用额外开辟的空间故而其空间复杂度为O(1)
3、例3 分析此算法会受其参数的影响即参数字符串的长度会影响这个算法完成任务所需要的时间既然字符串的长度不清楚便可以将字符串的长度看作为N
当在一个字符串中查找一个字符额时候可能一上来便找到了也有可能在中间位置才找到亦或许在字符串的结尾才能找到……显然会在字符串的哪个位置找到目标字符这也是未知的
对于时间复杂度来说关注的使这个算法最坏的情况故而此算法的时间复杂度为:O(N) ;
呼应上文所述概念 平均情况有什么特殊意义
大部分算法并不会看其平均情况即使看平均情况也是看一下这个算法大概会执行多少次例如希尔排序很少出现最坏的情况并且最坏的情况难以计算故而希尔排序这个算法会看其平均情况其平均情况的计算会使用到一个非常复杂的数学公式进行计算 常见的平均情况的计算方式 1、最好情况 最坏情况/2 2、按照概率计算(比较复杂) 4、例4: 二分查找 分析注意二分查找的逻辑
二分查找会利用到三个指针一个指向数组的最左一个指向数组的最右另外一个指向中间位置
让中间位置的数据与x 相比较当小于mid 的时候便缩小一半的查找范围调整left 到mid 右边的位置倘若大于mid 也会缩小一半的查找范围调整 right 到 mid 到左边的位置上而如若mid 所对应得数据等于所要查的数据x ,便代表着查找成功
显然我们也不知道所找的数据会在整个数组的哪个位置存在最好、平均、最坏的情况二分查找的特性每次查找没找到便会缩小一半的查找范围也就是说缩小了几次查找返回便意味着查找了多少次 最坏的情况就是在这个数组中找不到所找数据假设我们找了k 次那么 其中n 为这个数组中元素的个数,由式可得 ;所以此算法的时间复杂度为
当然由于该二分查找算法并没有使用额外的空间于是其空间复杂度为:O(1)
有关二分查找的知识补充 二分查找的查找效率非常高效但是这个算法是有缺陷的即必须在有序数组上才能进行查找倘若面对所要查找的数据是无序的那么首先就得排序然而排序也是一个非常消耗的过程 于是乎便有了后面的 树 -- 二叉树 -- 搜索二叉树 -- 平衡搜索二叉树 -- AVL Tree 、RBTree(红黑树) 这些算法无需排序也可以达到二分查找的高效以及还有更厉害的哈希表、b树系列.[ps:路漫漫……漫漫路……] 5、例5: 阶乘 分析递归便会利用到函数栈帧相关知识来理解 递归中基本代码的执行次数 递归次数 * 每次递归中基本代码的执行次数(看每次递归中有无循环) 为什么其空间复杂度为O(N)
该算法在执行的时候额外地开辟了空间 -- 函数栈帧的创建每调用一个函数便会创建对应的函数栈帧函数栈帧的开辟个数与递归的次数有关而在每个函数栈帧中均会使用常数个空间根据大O渐进表达式的规则故而其空间复杂度为O(N),图示如下 递归需要看栈帧的消耗即看递归的深度
6、例6: 斐波那契 分析 显然斐波那契函数Fib 也遵循: 递归中基本代码的执行次数 递归次数 * 每次递归中基本代码的执行次数(看每次递归中有无循环)
如上图所示Fib 的递归次数为一个等比数列求和并减去一个XX为假设缺少的常数个递归次数远小于前面的等比数列求和的所得值 根据大O渐进表达式因为(1X)远小于 2^n, 所以1X可以忽略故此算法的时间复杂度为: O(2^N); 空间复杂度
同理递归的空间复杂度看函数栈帧开辟的次数即递归的深度 再乘以每次递归中额外使用的空间Fib 的递归深度以大O渐进表达式为O(2^N) 并且每次递归中并没有使用额外的空间那么Fib 的空间复杂度便为 O(2^N)
其实不然因为 2^N 增长地很快一般情况在Linux 下建立一个进程的栈只有8M 倘若此算法的空间复杂度为 O(2^N) 栈肯定会溢出
实际上斐波那契函数(递归)是会重复利用空间的并且不累计 如上如所示会先计算一条分支然后再计算其他分支即斐波那契函数再创建栈帧的时候会先建立”一支“的栈帧直到这一支结束便销毁此支创建的函数栈帧……然后再继续调用下一支以实现重复利用空间那么此时的计算空间复杂度便是看的递归的深度即最多创建了多少函数栈帧故而斐波那契函数的空间复杂度为:O(N)
注递归是一条”支路“递归结束返回了再退回去递归另外一条”支路“
五、常见算法复杂度
常见算法的时间复杂度包括
常数时间复杂度(常数阶): O(1)对数时间复杂度(对数阶): O(log n)线性时间复杂度(线性阶): O(n)线性对数时间复杂度(线性对数阶): O(n log n)平方时间复杂度(平方阶): O(n^2)立方时间复杂度(立方阶): O(n^3)指数时间复杂度(指数阶): O(2^n) 总结
1、时间复杂度与空间复杂度的计算基于大O渐进表达式
2、大O符号Big O notation: 用于描述函数渐进行为的数学符号 推导大O阶方法 用常数1取代运行时间中的所有加法常数在修改后的运行次数函数中只保留最高阶项如果最高阶项存在并且不是1则去除与这个项目相乘的常数(让最高项的系数为1) 3、分析时间、空间复杂度的核心是梳理清楚整个代码的逻辑
