###二分法求数值x的整数n次幂
有o(logn )的方法吗？ 必须分成两部分来考虑。 这里的二分是指减少乘法的次数，省去重复的运算。 我求x的n次方。 那么，首先求x的n/2次方，把两个相乘。 像这样递归下去。
剑指邀请见16题第110页
###切波纳契Fibonacci数列的时间复杂度o(logn ) ) ) ) ) ) ) ) ) ) ) )。
来自3https://blog.csdn.net/weixin _ 40123831/article/details/80398996
//二分搜索
//
//时间复杂度： log2(n )==lg(N ) n ) ) (最坏的情况) ) ) ) ) ) ) )。
intbinarysearch(int*Array，int size，int data ) ) ) ) ) )。
{
输入左=0；
int right=size - 1；
intmid=left((right-left ) 1；
while(left=right ) /表示左闭右闭区间，可以获取边界的数值； 在leftright的情况下，表示左闭右开区间
{
if(data==Array[mid] ) ) ) )。
{
返回mid；
}
ELSEif(dataarray[mid] ) ) ) ) ) ) ) ) )。
{
right=mid - 1； //右边界改变很重要
}
else
left=mid 1；
}
返回- 1；
}见https://blog.csdn.net/beautyofmath/article/details/48184331
3359 blog.csdn.net/QQ _ 37703616/article/details/82120258
3358 emb.hqyj.com/column/column 365.htm
###二叉树检索的平均检索长为o(log2n )
导出过程为以下：
假设有一个双股排序树，总点数为n，高度为h，根节点的高度为1。
假设也是二叉树，则n和h的关系有式：n=(2^h )-1
即：h=log2(n1 )
对于高度为2、总点数为3的二叉树(二叉树)，搜索成功的平均搜索长度为：
ASL=(1*1)2)2)/3
对于高度为3、总点数为7的二叉树(二叉树)，搜索成功的平均搜索长度为：
ASL=(1*12*23*4)/7
是高度为h、总点数为n的二叉树(二叉树)，搜索成功的平均搜索长度为：
ASL=(1*12*23*4.h*2^ ) h-1 ) )/n[等式1]
对于[等式1]的1*1(2*2)3*4.h*2^ ) h-1 )
此数列包含h项：1 *2^ 0，2 *2^ 1，3 *2^ 2，h*2^(h-1 )
其总和S=1*2^0 2*2^1 3*2^2 . h*2^(h-1 ) [等式2]
等式两边乘以2等于：2 * s=1*2^ 12 *2^ 23 *2^3. (h-1 ) *2^(h-1 ) h*2^h[ (等式3 ) ]
[等式3]减去[等式2]等于：
s=h*2^h-(2^02^12^22^3.2) h-1 ) [等式4]
其中(2)0)2)2)3.2) ) h-1 ) )为等比数列的合计，为：
m=(2^02^12^22^3.2^ ) h-1 ) )
等式两边乘以2等于：2*m=(2^12^22^3.2^h ) )
两个等式被减去，有：M=2^h-1
将m代入[等式4]则：s=h*2^h-(2^h-1 )=) h-1 ) *2^h 1[等式5 )
由于h=log2(n1 )，所以将h代入[等式5]时，为：
s=[log2(n1 )-1]*2^[log2 ) n1]1
=[log2(n1 )-1]* ) n1 ) 1
=(n1 ) log2 ) n1 )-n
即s=(1*12*23*4.h*2^ ) h-1 ) ) n1 ) log2 ) n1 )-n
当将上述s代入[等式1]时，ASL=[(n 1 ) *log2(n1 )-n]/n
=[(n1 )/n]*log2 ) n1 )-1
因此，二叉树搜索成功的平均搜索长度为：
ASL=[[n1]/n]*log2[n1]-1[公式1]
其时间复杂度为：o(log2 ) n ) )
见3https://blog.csdn.net/Walden 1999/article/details/83659874
[代码]二叉树的平均检索长(ASL )的定义在此省略，但在此作为第一层的要素数(1第二层的要素数) 2第三层的要素数) 3……第n层的要素数) n )来计算。
时间复杂性问题1