数据结构和算法:时间复杂度和空间复杂度
2019-12-22 本文已影响0人
探索的码易
新技术的不断出现,使得程序猿们十分的焦虑,工作的单一让学到的新技术无法得到实质的实践,万变不离其宗,准备把数据结构和算法做一个系列博客的学习,分享他人也是学习的记录!
大 O时间时间复杂度:
T(n)=O(f(n)),O表示时间复杂度和代码运行次数有关系,可知的常量的系数是可以不考 虑的、O表示只和代码的运行次数成正比;一般情况下,只要算法中不存在循环语句、递归语句, 即使有成千上万行的代码,其时间复杂度也是Ο(1)
加法法则:取并列代码的 最大复杂度,如O(1)和O(2)取O(2)。
乘法法则:f1嵌套了f2 其复杂度为 O(f1*f2)
常见的时间复杂度:
1. O(1):复杂度是已经知道的,不随未知N 的增大而增大
2. O(m+n)、O(m*n) :不同代码块组成的复杂度,不能像加法那样可以省略,乘法还是适用用的;
2. O(logn)、O(nlogn): 对数阶时间复杂度,就是开方的次数
空间复杂度:
就是函数所占用计算机的空间:表示算法的存储空间与数据规模之间的增长最好时间复杂度:常见的有O(1),代码最少的运行次数
最坏时间复杂度:代码最多运行次数,O(n)
平均复杂度:所有可能发生的次数的概率相加 除以 总的可能性
均摊时间复杂度:有规律的平均复杂度、这种情况也只有在有规律的特性下能用到:很少用到,