遞歸

遞歸條件

• 自己調用自己
• 有結束條件

二分查找

二分查找對1~100亂序數字查找

l = list(range(1,101)) def bin_search(data_set,val):low = 0high = len(data_set) - 1while low <= high:mid = (low+high)//2if data_set[mid] == val:return midelif data_set[mid] < val:low = mid + 1else:high = mid - 1return n = bin_search(l,11) print(n) # 返回結果是： 10

時間復雜度、空間復雜度和穩定性

一個算法是由控制結構（順序、分支和循環3種）和原操作（指固有數據類型的操作）構成的，則算法時間取決于兩者的綜合效果。為了便于比較同一個問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作的重復執行的次數作為算法的時間量度。

時間復雜度的概念

一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度

常見的算法時間復雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

各種算法比較

空間復雜度概念

空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數據所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面

算法不穩定定義

在排序之前,有兩個數相等，但是在排序結束之后,它們兩個有可能改變順序.

說明：

在一個待排序隊列中,A和B相等,且A排在B的前面,而排序之后,A排在了B的后面.這個時候,我們說這種算法是不穩定的.

不穩定的幾種算法

• 快排為什么不穩定

　3 2 2 4 經過第一次快排后結果：2 2 3 4 （第3號位置的2第一次排序后跑到第1號位置了）

• 堆排序為什么不穩定

如果堆頂3先輸出，則，第三層的27（最后一個27）跑到堆頂，然后堆穩定，繼續輸出堆頂，是剛才那個27這樣說明后面的27先于第二個位置的27輸出，不穩定

• 選擇排序為什么不穩定

5 8 5 2 9 第一次假定1號位置的5最小，但是實際最小的是4號位置的2第一次排序后為：2 8 5 5 9 以前1號位置的5跑到3號位置5的后面了

空間，時間復雜度參考這個　　　　　　　
詳細鏈接參考這個鏈接

總結

以上是生活随笔為你收集整理的递归二分查找时间复杂度、空间复杂度和稳定性的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。