公司手机网站模板免费下载,沛县可以做网站的单位,厦门电脑网站建设,建设部网站政策法规如何衡量算法的好坏 根据时间复杂度和空间复杂度来判断 比较项目时间复杂度空间复杂度定义衡量算法执行时间与问题规模之间的关系衡量算法在运行过程中所占用的额外存储空间与问题规模之间的关系表达方式通常用大O符号表示#xff0c;如O#xff08;n#xff09;、O(n^2如On、O(n^2等通常用大O符号表示如On、O1等关注重点算法执行时间的增长速度算法所需额外空间的增长速度影响因素算法中基本操作的执行次数算法所需的额外数据结构占用的空间大小举例顺序查找的时间复杂度为 O (n)随着数据规模 n 的增大查找时间线性增长使用一个固定大小的变量空间复杂度为 O (1)使用一个长度为 n 的数组空间复杂度为 O (n)
大O的渐进表示法
【实例1】 推导大O阶方法
用常数1取代运行时间中所有的加法常数在修改后的运行次数函数中只保留最高阶项如果最高阶项存在且不为1则去除与这个项 相乘的常数得到的结果就是大O阶
使用大O的渐进表示法后Func1的时间复杂度为ON^2 我们平时所说的时间复杂度和空间复杂度都是在在最坏情况下的时间复杂度 拓展怎么计算平均时间复杂度 算平均时间复杂度就是把每种情况出现的概率乘以在这种情况下算法花的时间然后把所有这些结果加起来。 平均时间复杂度计算公式 常见时间复杂度计算举例
【实例1】知到循环次数的时间复杂度 【实例2】不知循环次数的时间复杂度 【实例3】常数次执行的时间复杂度 【实例4】冒泡排序的时间复杂度 小tips求复杂度一定要结合算法思想并不一定两个 for循环嵌套时间复杂度O(N)N^2 【实例5】二分查找的时间复杂度 【实例6】阶乘递归的时间复杂度 【实例7】斐波那契的时间复杂度 空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量空间复杂度算的是变量的个数使用大O渐进表示法。
通俗来讲空间复杂度就是看这个算法在运行过程中额外占用了多少内存空间。
【实例1】冒泡排序的空间复杂度
