大家好，折半查找时间复杂度相信很多的网友都不是很明白，包括有序表的折半查找算法也是一样，不过没有关系，接下来就来为大家分享关于折半查找时间复杂度和有序表的折半查找算法的一些知识点，大家可以关注收藏，免得下次来找不到哦，下面我们开始吧！
本文目录
- 二叉排序树与折半查找时间性能相不相同
- 折半查找的最坏情况下的时间复杂度是怎么推出来的求具体过程!
- 折半查找法快还是顺序查找快
- 折半查找的时间复杂度
- ...非递归两种折半查找程序,并分析其时间空间复杂度。
- 选择题 数据结构 折半搜索与二叉排序树的时间性能( )。
- 折半查找的时间复杂度是多少
一、二叉排序树与折半查找时间性能相不相同
折半查找：必须要求记录有序，采用顺序存储，利用这个特点，所以折半查找的效率也比顺序查找高，对于数量非常大时，非常快，时间复杂度为O(logN)。
二叉查找树：若它的左子树不为空，则左子树上所有节点的值均小于根节点。若它的右子树不为空，则右子树上所有节点的值均小于根节点，它的左右子树都是二叉查找树。
所以二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系。但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足logn的。
例如一棵只有多层左子树的而叉排序树。只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。
与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径 *** 问的最后一个结点的左孩子或右孩子结点。
2、查找树非空，将给定值key与查找树的根结点关键码比较。
3、若相等，查找成功，结束查找过程，否则：当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。
二、折半查找的最坏情况下的时间复杂度是怎么推出来的求具体过程!
1、二分查找因为每次都是从中间点开始查找，所以最坏情况是目标元素存在于最边缘的情况。
2、比如1~9，最坏情况就是1或者9，当然4,6这种也算是边缘（中心的边缘）。
3、因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
4、在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为
三、折半查找法快还是顺序查找快
1、不能笼统的说那个算法一定就好，算法分析要看条件和模型。
2、折半算法要求待查区域数据是已经排好序的，但是顺序查找没这个要求。
3、算法时间分析要看平均情况、最坏情况、更好情况的。更好情况两者时间一样，因为都是比较 *** 查找，都假定之一次比较就找到。最坏情况，折半查找更优为log n次比较，而顺序查找为n次比较。平均情况下（所有待查元素查找概率相当），一般是折半查找由于顺序查找（O(log n)< O(n)）。
4、一般数据规模稍大的测试、算法练习题，折半查找表现都很好，常常优于顺序查找，毕竟顺序查找算不上什么高等算法，优化空间很小。
5、但是，实际的查找操作很复杂，并不是查找数量多了就会趋近于平均情况，而且折半查找又要求有排序，所以仍然需要按照系统需求进行相应的数学分析和实际检测。
四、折半查找的时间复杂度
假设对n个元素的折半查找需要消耗的时间为t(n)。容易知道：
如果n> 1，则t(n)= t(n/2)+ c2
其中n/2需要取整，c1、c2都是常数
一直推演下去，直到n/(2的k次方)等于1，也就是k= log2(n)，此时等式变为：
于是时间复杂度为log2(n)。注意log2(n)和log(n)其实是同样的复杂度，因为它们之间仅仅差了一个常量系数而已。
这个是不严格的推导，因为没有考虑整数除以2之后可能有余数的情况。但即使有余数，也是不影响时间复杂度的。
递归折半查找的时间复杂度是O(log2n)，空间复杂度是O(log2n)，也是递归的更大深度
非递归的时间复杂度是O(log2n)，空间复杂度是O(1)，仅仅用几个单变量就够了
五、...非递归两种折半查找程序,并分析其时间空间复杂度。
1、折半查找需要先对数据进行排序。
2、intbSearch(intdata[],constintx,intbeg,intlast)
3、intrBSearch(intdata[],constintx,intbeg,intlast)
4、 returnrBSearch(data,x,beg,mid-1);
5、 returnrBSearch(data,x,mid+1,last);
6、 cout<<"Thearrayis:"<<endl;
7、 intn=sizeof(data)/sizeof(int);
8、 cout<<data[i]<<"";
9、//index=bSearch(data,num,0,n);
10、 index=rBSearch(data,num,0,n);
11、 cout<<"Indexof"<<num<<"is"<<index<<endl;
12、}
以上是冒泡排序算法的实现。
13、在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：
14、1）待查找数据值与中间元素值正好相等，则放回中间元素值的索引。
15、2）待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。
16、3）待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值
17、4）如果最后找不到相等的值，则返回错误提示信息。
18、intbSearch(intdata[],constintx,intbeg,intlast)
19、intrBSearch(intdata[],constintx,intbeg,intlast)
20、 returnrBSearch(data,x,beg,mid-1);
21、 returnrBSearch(data,x,mid+1,last);
22、 cout<<"Thearrayis:"<<endl;
23、 intn=sizeof(data)/sizeof(int);
24、 cout<<data[i]<<"";
25、//inedx=bSearch(data,num,0,n);
26、 index=rBSearch(data,num,0,n);
27、 cout<<"Indexof"<<num<<"is"<<index<<endl;
28、折半查找就像搜素二叉树：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为log2(n+1)-1，其算法复杂度为O(log(n))。
六、选择题 数据结构 折半搜索与二叉排序树的时间性能( )。
1、折半查找复杂度恒定是log2n，但二叉排序树更优时间复杂度是log2n，只有平衡二叉树才是log2n。
2、折半查找：必须要求记录有序，采用顺序存储，利bai用这个特点，所以折半查找的效率也比顺序查找高，对于数量非常大时，非常快，时间复杂度为O(logN)。
3、二叉查找树：若它的左子树不为空，则左子树上所有节点的值均小于根节点。若它的右子树不为空，则右子树上所有节点的值均小于根节点，它的左右子树都是二叉查找树。
4、二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2]，则只要在数组a的左半部分继续搜索x,如果x>a[n/2]，则只要在数组a的右半部搜索x。
5、时间复杂度即是while循环的次数。
6、渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
7、可得k=log2n,（是以2为底，n的对数）
8、所以时间复杂度可以表示O(h)=O(log2n)
9、参考资料来源：百度百科-二分查找
七、折半查找的时间复杂度是多少
假设对n个元素的折半查找需要消耗的时间为t(n)。容易知道：
如果n> 1，则t(n)= t(n/2)+ c2
其中n/2需要取整，c1、c2都是常数
一直推演下去，直到n/(2的k次方)等于1，也就是k= log2(n)，此时等式变为：
于是时间复杂度为log2(n)。注意log2(n)和log(n)其实是同样的复杂度，因为它们之间仅仅差了一个常量系数而已。
这个是不严格的推导，因为没有考虑整数除以2之后可能有余数的情况。但即使有余数，也是不影响时间复杂度的。
OK，本文到此结束，希望对大家有所帮助。
