搜尋
首頁常見問題一個運用二分查找演算法的程式的時間複雜度是什麼

一個運用二分查找演算法的程式的時間複雜度是「對數等級」。二分查找是一種效率較高的查找方法,演算法複雜度即是while迴圈的次數,時間複雜度可以表示「O(h)=O(log2n)」。

一個運用二分查找演算法的程式的時間複雜度是什麼

本教學操作環境:windows7系統、Dell G3電腦。

一個運用二分查找演算法的程式的時間複雜度是「對數層級」。

相關推薦:《程式設計學習

二分查找也稱為折半查找(Binary Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須採用順序儲存結構,且表格中元素依關鍵字有序排列。

查找過程:

首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與尋找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重複以上過程,直到找到符合條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。

演算法複雜度:

二分查找的基本想法是將n個元素分成大致相等的兩部分,取a[n/2]與x做比較,如果x=a[n/2],則找到x,演算法中止;如果xa[n/2] ,則只要在陣列a的右半部搜尋x.

時間複雜度即是while循環的次數。

總共有n個元素,

漸漸跟下去就是n,n/2,n/4,....n/2^k(接下來運算元素的剩餘個數),其中k就是循環的次數

由於你n/2^k取整後>=1

即令n/2^k=1

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

所以時間複雜度可以表示O(h)=O(log2n)

下面提供一段二分查找實現的偽代碼:

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

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

想要查閱更多相關文章,請造訪PHP中文網! !

以上是一個運用二分查找演算法的程式的時間複雜度是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

mPDF

mPDF

mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。