天津自贸区建设局网站,如何建设一个视频网站,杭州做网站的优质公司哪家好,济南市做网站公司文章目录前言时间复杂度1.概述2.大O记法3.常见类型空间复杂度1.概述2.常见类型典型算法的复杂度分析1.递归算法2.哈希表前言
我们知道#xff0c;研究算法的最终目的就是如何花更少的时间#xff0c;如何占用更少的内存去完成相同的需求。
时间复杂度
1.概述
我们要计算算…
文章目录前言时间复杂度1.概述2.大O记法3.常见类型空间复杂度1.概述2.常见类型典型算法的复杂度分析1.递归算法2.哈希表前言
我们知道研究算法的最终目的就是如何花更少的时间如何占用更少的内存去完成相同的需求。
时间复杂度
1.概述
我们要计算算法时间耗费情况但我们并不能将时间占用和空间占用量化。所以我们得度量算法的执行时间那么如何度量呢
我们分析一个算法的运行时间最重要的就是把核心操作的次数和输入规模关联起来。
2.大O记法
在进行算法分析时语句总的执行次数T(n)是关于问题规模n的函数进而分析T(n)随着n的变化情况并确定T(n)的量级。
算法的时间复杂度就是算法的时间量度记作:T(n)O(f(n))。它表示随着问题规模n的增大算法执行时间的增长率和f(n)的增长率相同称作算法的渐近时间复杂度简称时间复杂度其中f(n)是问题规模n的某个函数。
所以计算时间复杂度主要分两步统计操作数量判断渐进上界 常用技巧 1用常数1取代运行时间中的所有加法常数 2在修改后的运行次数中只保留高阶项 3如果最高阶项存在且常数因子不为1则去除与这个项相乘的常数
3.常见类型
首先常见的时间复杂度类型排序
O(1)O(logn)O(n)O(nlogn)O(n^2) O(2^n) O(n!) 空间复杂度
1.概述
统计 算法使用内存空间随着数据量变大时的增长趋势.
通常情况下空间复杂度统计范围是「暂存空间」「输出空间」
2.常见类型
同样是用大O来表示只是这个是表示使用空间大小
O(1)O(logn)O(n)O(n^2) O(2^n)
典型算法的复杂度分析
1.递归算法
1时间复杂度 子问题个数乘以解决一个子问题需要的时间即递归的次数 * 每次递归中的操作次数。 例如斐波那契数列 2空间复杂度
2.哈希表
空间换时间查找的时间复杂度是O(1)
参考链接https://www.helloalgo.com/chapter_computational_complexity/space_complexity/#232 https://programmercarl.com
