时间复杂度中的O(logN)

N的增长要快于log的任意的幂。对数(logN)最常出现的规律可概括为下列一般法则:如果一个算法用常数时间将问题的大小消减为其一部分(通常为1/2)(例如分治算法),那么该算法就是O(logN)。另一方面,如果使用常数时间只是把问题减少一个常数的数量(如将问题减少1),那么这种算法就是O(N)的。

 

时间复杂度中的O(logN)的例子

1.折半查找

给定一个整数X和整数A0,A1,···,AN-1,后者是已经预先排序并存在内存中,求下标i使得Ai=X,如果X不在数据中,则返回i=-1。

循环从high-low=N-1开始并在high-low<=-1结束。每次循环后high-low的值至少将该次循环前的值折半;于是,循环的次数最多为log(N-1)+2。(例如,若high-low=128,则在歌词迭代后high-low的最大值是64,32,16,8,4,2,1,0,-1)因此,运行时间是O(logN)。

 

2.欧几里得算法(辗转相除法)

计算最大公因数的欧几里得算法。两个整数的最大公因数(gcd)是同时整除二者的最大整数。

连续计算余数直到余数是0为止,最后的非零余数就是最大公因数。例如M=1989和N=1590,则余数序列是399,393,6,3,0,从而两者的最大公因数是3。

 

3.幂运算

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注