一個運用二分查找算法的程序的時間復(fù)雜度指的是什么-創(chuàng)新互聯(lián)

小編給大家分享一下一個運用二分查找算法的程序的時間復(fù)雜度指的是什么，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

成都創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、晉城網(wǎng)絡(luò)推廣、微信小程序開發(fā)、晉城網(wǎng)絡(luò)營銷、晉城企業(yè)策劃、晉城品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎；成都創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供晉城建站搭建服務(wù)，24小時服務(wù)熱線：18982081108，官方網(wǎng)址：muchs.cn

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

一個運用二分查找算法的程序的時間復(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,算法中止；如果x<a[n/2],則只要在數(shù)組a的左半部分繼續(xù)搜索x,如果x>a[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-<(max+min)/2
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，算法終止；如 果x<a[n/2]，則我們只要在數(shù)組a的左半部繼續(xù)搜索x；如果x>a[n/2]，則我們只要在數(shù)組a的右 半部繼續(xù)搜索x。

以上是“一個運用二分查找算法的程序的時間復(fù)雜度指的是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

分享標題：一個運用二分查找算法的程序的時間復(fù)雜度指的是什么-創(chuàng)新互聯(lián)
鏈接分享：http://muchs.cn/article46/depoeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、搜索引擎優(yōu)化、品牌網(wǎng)站建設(shè)、移動網(wǎng)站建設(shè)、微信公眾號、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)