读书笔记：《算法图解》第一章 算法简介

二分查找#

二分查找是对半查找，进队列表是有序时有效。

n个元素的列表，二分查找最多需要$lo{g}_{2}n$ 步，简单顺序查找最多需要n步。

对数#

对数：对数运算是幂运算的逆运算

$N=a^x(a>0,a\ne 1)$, $x$就是$a$为底$N$的对数，记作$x={\log }_{a}N$,其中：

• $a$ : 底
• $N$ : 真数
• $x$ : 以$a$为底$N$的对数

幂：

log 指的都是 ${\log }_2$

$\log 8$ = ${\log }_{2}8$ = 3 ($2^3=8$)

1. 以10为底的对数称为常用对数,记为$\lg$
2. 以无理数$e$($e=2.71828\dots$)为底的对数称为自然对数，记为$\ln$
3. 零没有对数
4. 实数范围内，负数没有对数；复数范围内，负数有对数

时间复杂度#

简单顺序查找的实践复杂度 $O\left(n\right)$

二分查找的时间复杂度 $O\left(\log n\right)$

时间复杂度表示了最糟糕情况下的运行时间

常用时间复杂度#

• $O\left(\log n\right)$ 对数时间
• $O\left(n\right)$ 线性时间
• $O(n\times \log n)$
• $O\left(n^2\right)$
• $O(n!)$ n的阶乘

原帖地址