二分查找是对半查找，进队列表是有序时有效。
n个元素的列表，二分查找最多需要log2nlog2n 步，简单顺序查找最多需要n步。
对数#
对数：对数运算是幂运算的逆运算
N=ax(a>0,a≠1)N=ax(a>0,a≠1), xx就是aa为底NN的对数，记作x=logaNx=logaN,其中：
- aa : 底
- NN : 真数
- xx : 以aa为底NN的对数
幂：
log 指的都是 log2log2
log8log8 = log28log28 = 3 (23=823=8)
- 以10为底的对数称为常用对数,记为lglg
- 以无理数ee(e=2.71828…e=2.71828…)为底的对数称为自然对数，记为lnln
- 零没有对数
- 实数范围内，负数没有对数；复数范围内，负数有对数
时间复杂度#
简单顺序查找的实践复杂度 O(n)O(n)
二分查找的时间复杂度 O(logn)O(logn)
时间复杂度表示了最糟糕情况下的运行时间
常用时间复杂度#
- O(logn)O(logn) 对数时间
- O(n)O(n) 线性时间
- O(n×logn)O(n×logn)
- O(n2)O(n2)
- O(n!)O(n!) n的阶乘
网友评论