一個運用二分查找算法的程序的時間復(fù)雜度是“對數(shù)級別”。二分查找是一種效率較高的查找方法，算法復(fù)雜度即是while循環(huán)的次數(shù)，時間復(fù)雜度可以表示“O(h)=O(log2n)”。

本教程操作環(huán)境：windows7系統(tǒng)、Dell G3電腦。

一個運用二分查找算法的程序的時間復(fù)雜度是“對數(shù)級別”。

相關(guān)推薦：《編程學習》

二分查找也稱折半查找(Binary Search)，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

查找過程：

首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

算法復(fù)雜度：

二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果xa[n/2],則只要在數(shù)組a的右半部搜索x.

時間復(fù)雜度即是while循環(huán)的次數(shù)。

總共有n個元素，

漸漸跟下去就是n,n/2,n/4,....n/2^k(接下來操作元素的剩余個數(shù))，其中k就是循環(huán)的次數(shù)

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,(是以2為底，n的對數(shù))

所以時間復(fù)雜度可以表示O(h)=O(log2n)

下面提供一段二分查找實現(xiàn)的偽代碼:BinarySearch(max,min,des)

mid-

while(min<=max)

mid=(min+max)/2

if mid=des then

return mid

elseif mid >des then

max=mid-1

else

min=mid+1

return max

折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)。它的基本思想是：(這里假設(shè)數(shù)組元素呈升序排列)將n個元素分成個數(shù)大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止；如 果xa[n/2]，則我們只要在數(shù)組a的右 半部繼續(xù)搜索x。

想要查閱更多相關(guān)文章，請訪問PHP中文網(wǎng)！！

總結(jié)

以上是生活随笔為你收集整理的php二分查找算法时间复杂度,一个运用二分查找算法的程序的时间复杂度是什么...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。