时间复杂度(time-complexity)与O(log n)

在计算机科学中,时间复杂度代表了计算复杂度,它描述了运行算法所花费的时间。

假设每个基本运算都需要固定的时间来执行,通过计算算法执行的基本运算的数量来估算时间复杂度。

算法所花费的时间量和执行的基本运算的数量最多相差一个恒定因子。

对数的定义

对数的定义:表示要得到指定的数字,须增加一个固定数字(基数)幂的数量。

说人话就是:对数回答了这样一个问题:“我们要乘以多少个这样的数字来得到那个数字?”。

如果x的y次方等于n(x>0,且不等于1),那么,y叫做以x为底n的对数(logarithm)。记作logx=y,其中,x叫做对数的底数。

问:要乘多少个2才能得到8?

答:2×2×2 = 8,要乘以3个2才能得8。

所以,以2为底8的对数是3。

log n

1.底数为2时,在计算机领域,写为log,也就是不写底数,logN即log2n。

2.底数为10时,写为lg;

3.底数为e时,称为自然对数,写为ln;

时间复杂度 O(log n) 

Big O notation一般用于描述算法的复杂程度。与成绩分A、B、C一样。

可以将它看成函数y= f(x)。

O(n)中的n代表规模大小,表明了时间复杂度跟规模的关系。

如果不希望计算机花费大量的时间去执行一个运算,尽量将big O降到最小。

1,2,3,4,5,6,7属于常数,O(1)。

n,2n,2n+1,4m+4,属于线性函数,O(n)。

n^2 4n^2+3,属于二次的线性函数,O(n^2)。


注,时间复杂度是个近似值,比如O(2N)是O(N),O(3N+5)也是O(N),此值表达的是复杂度趋势。

举例说明

以二分查找说明时间复杂度。一个由16个元素组成的数组。

使用二分查找法的过程及公式

与中间项每次比较之后,搜索范围减半。在16个元素中搜索数字,须将数组除以4。简化后的公式如下:

对于n个元素的公式如下:

经过分解后,最终如下:

由对数的定义,将公式变化为如下所示: