什麼是這個僞代碼的大O？我還需要一個適當的解釋

Question

這是我想要計算時間複雜度的僞代碼，我認爲它是一種二分搜索算法，但是當計算複雜性時我失敗了，因爲它正在減少logarithamic。

USE variables half-array,found,middle element 
    SET half-array=initial array; 
    SET found=True; 

Boolean SearchArray(half-array) 

    find middle element in half-array; 
    Compare search key with middle element; 
    IF middle element==search key THEN 
      SET found=True; 
    ELSE 
     IF search key< middle element THEN 
      SET half-array=lower half of initial array; 
     ELSE 
      SET half-array=upper half of initial array; 


SearchArray(half-array) 

Answer 1

看起來你正在遞歸地運行這個方法，並且每次迭代都會減少搜索到的元素數量的一半。這將是一個對數減少，即O（log n）。

由於您將元素每次減少一半，因此您需要確定需要多少次執行才能將其減少爲單個元素，其中this previous answer提供了一個證明，或者如果您是一個更直觀的人，則可以使用從this response如下圖：

Answer 2

是的，這的確是一個二進制搜索algorithm.The它之所以被稱爲「二進制」的搜索是因爲，如果你會注意到，在每次迭代後，您問題空間減少了大約一半（我大概是因爲地板功能）。 所以現在，爲了找到複雜性，我們必須設計一個遞歸關係，我們可以使用它來確定二進制搜索的最壞情況時間複雜度。

設T（n）表示比較n個elements.In最壞的情況下二進制搜索確實的數目，沒有元素是found.Also，使我們的分析更簡單，假設n爲2

電源

二進制搜索：

1. 當有一個單獨的元件，僅存在一個檢查，因此T（1）= 1。

2. 它計算中間條目然後將其與我們的比較如果它等於該鍵返回索引，否則通過更新上下限使得範圍減半，使得n/2個元素在該範圍內。

3. 然後，我們只檢查兩個半部分中的一個，這是遞歸完成的，直到剩下一個元素。

因此，我們得到的遞推關係：

T（N）= T（N/2）+ 1

使用主定理，我們得到的時間複雜度是T（N）∈Θ（log n）的

另請參考：Master Theorem

Answer 3

你是科爾這個算法是二進制搜索（比較你的僞代碼和這個維基頁面上的僞代碼頁面：Binary Search）

在這種情況下，該算法的最壞情況時間複雜度爲O（log n），其中n是給定數組中元素的數量。這是因爲，在每次遞歸調用中，如果沒有找到目標元素，則將數組分成兩半。

這個約簡過程是對數的，因爲在這個算法的最後，你將通過將仍然需要檢查的元素數量除以2來將列表減少到單個元素 - 你做的次數是大致相當於（見下文）您必須自行乘以2以獲得等於給定數組大小的數目的次數。

*我說大致上面是，因爲遞歸調用的次數總是一個整數值，而如果給定列表的大小是2，那麼將不會是整數不是兩個冪。