我想问问那个二分法查找的问题!时间复杂度有两种度量方法!一种是平均性态表示,还有一种是最坏情况复杂度!二分法查找是以最坏情况复杂度来计量的吧?书上说是【log(2)n】次比较可以查

来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/22 04:56:38
我想问问那个二分法查找的问题!时间复杂度有两种度量方法!一种是平均性态表示,还有一种是最坏情况复杂度!二分法查找是以最坏情况复杂度来计量的吧?书上说是【log(2)n】次比较可以查我想问问那个二分法查

我想问问那个二分法查找的问题!时间复杂度有两种度量方法!一种是平均性态表示,还有一种是最坏情况复杂度!二分法查找是以最坏情况复杂度来计量的吧?书上说是【log(2)n】次比较可以查
我想问问那个二分法查找的问题!
时间复杂度有两种度量方法!一种是平均性态表示,还有一种是最坏情况复杂度!二分法查找是以最坏情况复杂度来计量的吧?书上说是【log(2)n】次比较可以查出结果!假设有偶数个数a1,a2……an;n是个偶数!按照那个二叉树的形式排列!设有k行数字!k行的数的个数是k-1行个数的两倍(就是在一次查找不成功,下次的查找范围是第一次的一半),构成一个金字塔!最上面的数字只有一个,比较的次数就是金字塔的行数把?根据数学运算,行数应该是【log(2)n】+1啊!同时那个二分法查找的时间复杂度应该是【log(2)n】+1.不知道我的分析出错在哪里?

我想问问那个二分法查找的问题!时间复杂度有两种度量方法!一种是平均性态表示,还有一种是最坏情况复杂度!二分法查找是以最坏情况复杂度来计量的吧?书上说是【log(2)n】次比较可以查
二叉树查找:条件是需要数据进行有目的的分叉(左小右大或左大右小),是通过干预使这些数按固有的方式划分,它的起点是塔顶的数据. 二分法查找:条件是需要排序(从大到小或从小到大)的,通过排序达到一种自然中分的方式,它的起点很自然就是有序序列中间位置的数据. 两者查询的速度是一样的(都是循环把数据分开两部份判断),但是查询同一个数所需要的时间不一定相同,因为两者的起点和寻找方式存在不一致的状况. 当然要使它们一致也有方法,将二叉树的节点按二分法取中间的方式排布,两者则一致,查询时间相同.然而这对二叉数查询是多余的.