二分查找的时间与空间，算法好坏衡量
时间复杂度，算法好坏衡量
定义
用于衡量一个算法的执行，随数据规模增大，而增长的时间成本。（不依赖环境因素）
具体表现
假设算法要处理的数据规模是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，表达式中相乘的常量可以省略，比如上文线性查找：3∗n，3可以省略，因为函数g(n)总是要乘一个常数。2，多项式中数量规模更小的(低次项)的表达式，比如存在：n2+n,那么则忽略n。3，不同底数的对数，渐进上界可以用一个对数函数log2(n)表示，比如：存在函数log2(n),可以被替换为lg(n)，因为log2(n)=lg(n)/lg(2),相乘的常量1/lg(2)可以省略。这步是换底公式logab=logcb/logca。4，对数的常数次幂可以省略，比如log(nc)=c∗log(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)。