算法的时间复杂度
本帖最后由 影-死神 于 2018-10-11 23:05 编辑时间复杂度的定义
算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，
使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
时间复杂度的数量级（升序）
1、log2n、 n、 n*log2n、n2、n3、2n、n!、nn
简易判断方法
只有顺序执行，没有循环和递归等则时间复杂度为1；
如果有二分则时间复杂度为O(log2n)，二分例如快速幂、二分查找；
如果算法中存在for循环，则看有几重for循环：
只有一重则时间复杂度为O(n)，
二重则时间复杂度为O(n2)，依此类推......
如果一个for循环套一个二分，那么时间复杂度则为O(n*logn)；
简单的二分递归的时间复杂度为2n，
二分递归即每次递归分成两份分别递归，并且递归变量相对于上次递归减少1。
页:
[1]