算法的时间复杂度

影-死神

时间复杂度的定义
算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，
使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

时间复杂度的数量级（升序）
1、log₂n、 n、 n*log₂n、n²、n³、2ⁿ、n!、nⁿ

简易判断方法
只有顺序执行，没有循环和递归等则时间复杂度为1；
如果有二分则时间复杂度为O(log₂n)，二分例如快速幂、二分查找；
如果算法中存在for循环，则看有几重for循环：
只有一重则时间复杂度为O(n)，
二重则时间复杂度为O(n²)，依此类推......
如果一个for循环套一个二分，那么时间复杂度则为O(n*logn)；
简单的二分递归的时间复杂度为2ⁿ，
二分递归即每次递归分成两份分别递归，并且递归变量相对于上次递归减少1。