二分查找的时间与空间,算法好坏衡量

avatar
作者
筋斗云
阅读量:1

时间复杂度,算法好坏衡量

定义

用于衡量一个算法的执行,随数据规模增大,而增长的时间成本。(不依赖环境因素)

具体表现

假设算法要处理的数据规模是n,代码总的执行行数用f(n)来表示。

比如:

线性查找算法函数f(n)= 3*n+3

二分查找算法函数f(n)=(floor(log_2(n))+1)*5+4
请添加图片描述

如上分别是:渐进上界O(g(n)),渐进下界O(Ω(n)),渐进紧界 c,c1,c2都是常数 f(n)实质性代码行数与n的函数 g(n)是经过化简,变化趋势与f(n)一致的函数 

渐进上界

举例

线性查找:

f(n)=3*n+3  g(n)=n(把原函数f(n)拆开当做多项式,最高项就是g(n))  若取c=4,在n=3之后g(n)可以作为原函数f(n)的渐进上界,那么就可以写作O(n)。 

二分查找:

f(n)=5*floor(log_2(n))+9 g(n)=log_2(n) O(log_2(n)) 
规则

对于 f ( n ) 来说,求 g ( n ) 1 ,表达式中相乘的常量可以省略,比如上文线性查找: 3 ∗ n , 3 可以省略,因为函数 g ( n ) 总是要乘一个常数。 2 ,多项式中数量规模更小的 ( 低次项 ) 的表达式,比如存在: n 2 + n , 那么则忽略 n 。 3 ,不同底数的对数,渐进上界可以用一个对数函数 l o g 2 ( n ) 表示,比如:存在函数 l o g 2 ( n ) , 可以被替换为 l g ( n ) ,因为 l o g 2 ( n ) = l g ( n ) / l g ( 2 ) , 相乘的常量 1 / l g ( 2 ) 可以省略。这步是换底公式 l o g a b = l o g c b / l o g c a 。 4 ,对数的常数次幂可以省略,比如 l o g ( n c ) = c ∗ l o g ( n ) 对于f(n)来说,求g(n) 1,表达式中相乘的常量可以省略,比如上文线性查找:3*n,3可以省略,因为函数g(n)总是要乘一个常数。 2,多项式中数量规模更小的(低次项)的表达式,比如存在:n^2+n,那么则忽略n。 3,不同底数的对数,渐进上界可以用一个对数函数log_2(n)表示,比如:存在函数log_2(n),可以被替换为lg(n),因为log_2(n)=lg(n)/lg(2),相乘的常量1/lg(2)可以省略。这步是换底公式log_a b = log_c b/log_c a。 4,对数的常数次幂可以省略,比如log(n^c)=c*log(n) 对于f(n)来说,求g(n)1,表达式中相乘的常量可以省略,比如上文线性查找:3n3可以省略,因为函数g(n)总是要乘一个常数。2,多项式中数量规模更小的(低次项)的表达式,比如存在:n2+n,那么则忽略n3,不同底数的对数,渐进上界可以用一个对数函数log2(n)表示,比如:存在函数log2(n),可以被替换为lg(n),因为log2(n)=lg(n)/lg(2),相乘的常量1/lg(2)可以省略。这步是换底公式logab=logcb/logca4,对数的常数次幂可以省略,比如log(nc)=clog(n)

常见算法大O表示

请添加图片描述

黑色横线O(1):常量时间,算法不随着数据规模而变化 绿色O(log(n)):对数时间 蓝色O(n),线性时间没算法时间与数据规模成正比 橙色O(n*log(n)),拟线性时间,相近线性时间 红色O(n^2),平方时间 黑色朝上O(2_n),指数时间 未画出的O(n!),巨大变化,最高时间复杂度 

渐进下界

下方线表示该算法的最优情况,从某个常数n_0开始,cg(n)就一直处于f(n)下方,那么记作Ω(g(n))
请添加图片描述

渐进紧界

从某个常数n开始,f(n)总是处于c1 * g(n)与c2 * g(n)之间,那么记作θ(g(n)),既能代表该代码执行的最优情况也可以代表最差情况。(注意这个符号念xi 二声 ta 一声)
请添加图片描述

空间复杂度,算法好坏衡量

定义

与时间复杂度类似,一般也是用大O表示发来衡量:一个算法执行随数据规模增大,而增长的额外占用空间成本

具体表现

举例

    private static int binarySearchBasic(int[] a,int target){         //不看原始数据,看新增,这里不看“int[] a,int target”         int i = 0,j = a.length - 1;         //这里i和j指针各占4字节         while(i<=j){             int m = (i + j) / 2;             if (target < a[m]){                 j = m - 1;//目标小于中间值             } else if(target > a[m]){                 i = m + 1;//目标大于中间值             }else{                 return m;             }         }         //循环占用4字节(m)         return -1;     } 

总计 12 字节也就是 o ( 1 ) , 常量时间,不会随着 n 的变化而变化。 总计12字节也就是o(1),常量时间,不会随着n的变化而变化。 总计12字节也就是o(1),常量时间,不会随着n的变化而变化。

二分查找性能分析

时间复杂度

最坏情况:O(log n)

最好情况:如果待查找元素恰好在数组中央,只需要循环一次O(1)

空间复杂度

计12字节也就是o(1),常量时间,不会随着n的变化而变化。
$$

二分查找性能分析

时间复杂度

最坏情况:O(log n)

最好情况:如果待查找元素恰好在数组中央,只需要循环一次O(1)

空间复杂度

需要常数个指针i,j,m,因此额外占用的空间是O(1)。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!