常見演算法

基礎演算法

• 基礎演算法
  • 演算法基礎
    • 演算法的定義和特征
    • 演算法設計的要求
    • 演算法的時間復雜度
    • 演算法空間復雜度
  • 排序二叉樹
  • 二分查找
  • 冒泡排序
  • 選擇排序
  • 插入排序
  • 希爾排序
  • 快速排序

演算法基礎

• 演算法的定義和特征

# 一個計算程序,解決問題的方法
- 解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制,
能夠對一定規范的輸入，在有限時間內獲得所要求的輸出,如果一個演算法有缺陷，或不適合于某個問題，執行這個演算法
將不會解決這個問題,不同的演算法可能用不同的時間、空間或效率來完成同樣的任務，一個演算法的優劣可以用空間復雜度與時間復雜度來衡量.
# 特征
- 有窮性：演算法的有窮性是指演算法必須能在執行有限個步驟之后終止
- 確切性：演算法的每一步驟必須有確切的定義
- 輸入項：一個演算法有0個或多個輸入，以刻畫運算物件的初始情況，所謂0個輸入是指演算法本身定出了初始條件
- 輸出項：一個演算法有一個或多個輸出，以反映對輸入資料加工后的結果，沒有輸出的演算法是毫無意義的；
- 可行性：演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性），

• 演算法設計的要求

- 確定性: 指的是演算法至少應該有輸入,輸出和加工處理無歧義性，能正確反映問題的需求,能夠得到問題的正確答案，
- 確定性大體分為四個層次:
    1.演算法程式無語法錯誤;
    2.演算法程式對于合法的輸入產生滿足要求的輸出;
    3.對于非法輸入能夠產生滿足規格的說明;
    4.演算法程式對于故意刁難的測驗輸入都有滿足要求的輸出結果，

- 可讀性: 程式便于閱讀,理解交流，
- 健壯性: 當輸入資料不合法時,演算法也能作出相關處理，而不是產生例外,崩潰或者莫名其妙的結果，時間效率高和存盤量低

• 演算法的時間復雜度

# 定義
- 在進行演算法分析時，陳述句總的執行次數T(n)是關于問題規模n的函式，進而分析T(n)隨n的變化情況并確定T(n)的數量級.
- 演算法的時間復雜度，也就是演算法的時間量度，記作：T(n)=0(f(n))
- 它表示隨問題規模n的增大，演算法執行時間的埔長率和 f(n)的埔長率相同，稱作演算法的漸近時間復雜度，簡稱為時間復雜度，
其中f( n)是問題規橫n的某個函式.

# 求解演算法的時間復雜度的具體步驟
- 找出演算法中的基本陳述句 (演算法中執行次數最多的那條陳述句就是基本陳述句，通常是最內層回圈的回圈體)
- 計算基本陳述句的執行次數的數量級(只需計算基本陳述句執行次數的數量級，這就意味著只要保證基本陳述句執行次數的函式中的最高次冪正確即可，
可以忽略所有低次冪和最高次冪的系數，這樣能夠簡化演算法分析，并且使注意力集中在最重要的一點上：增長率)
- 用大Ο記號表示演算法的時間性能(將基本陳述句執行次數的數量級放入大Ο記號中)

# 推導大o階的基本的推導方法：
- 用常數1取代運行時間中的所有加法常數，
- 在修改后的運行次數函式中，只保留最髙階項，
- 如果最高階項存在且不是1,則去除與這個項相乘的常數，簡單的說，就是保留求出次數的最高次冪，并且把系數去掉， 如T(n)=n2+n+1 =O(n2)

#復雜度O(1) print("this is wd") 
#復雜度O(n) for i in range(n): print(i) 
#復雜度O(n2) for i in range(n): for j in range(n): print(j) 
#復雜度O(n3) for i in range(n): for j in range(n): for k in range(n): print('wd') 
#復雜度O(log2n) while n > 1: print(n) n = n // 2

#  常見的復雜度按效率排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2nlogn)<O(n2) 

• 演算法空間復雜度

# 空間復雜度(Space Complexity)是對一個演算法在運行程序中臨時占用存盤空間大小的量度(三個方面)
- 包括存盤演算法本身所占用的存盤空間(存盤演算法本身所占用的存盤空間與演算法書寫的長短成正比，要壓縮這方面的存盤空間，就必須撰寫出較短的演算法)
- 演算法的輸入輸出資料所占用的存盤空間(演算法的輸入輸出資料所占用的存盤空間是由要解決的問題決定的，
是通過引數表由呼叫函式傳遞而來的，它不隨本演算法的不同而改變)
- 演算法在運行程序中臨時占用的存盤空間(演算法在運行程序中臨時占用的存盤空間隨演算法的不同而異，有的演算法只
需要占用少量的臨時作業單元，而且不隨問題規模的大小而改變，這種演算法是節省存盤的演算法；有的演算法需要
占用的臨時作業單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存盤單元)
- 具體表述
    1.當一個演算法的空間復雜度為一個常量，即不隨被處理資料量n的大小而改變時，可表示為O(1)；
    2.當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為0(log2n)；
    3.當一個演算法的空間復雜度與n成線性比例關系時，可表示為0(n).若形參為陣列，則只需要為它分配一個存盤由實
    4.參傳送來的一個地址指標的空間，即一個機器字長空間；若形參為參考方式，則也只需要為其分配存盤一個地
    5.址的空間，用它來存盤對應實參變數的地址，以便由系統自動參考實參變數，

排序二叉樹

# 使用二叉樹 alist = [3,8,5,7,6,2,9,4,1] 進行排序
亂序資料的插入的時候，需要遵從一個準則：
- 插入的第一個數值作為樹的根節點
- 后序插入的數值，如果比根節點小，插入根節點的左側，否則插入到根節點的右側
- 使用深度優先中序遍歷

# 代碼
class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None  
class SortTree():
    def __init__(self):
        self.root = None
    def add(self,item):
        node = Node(item)
        cur = self.root
        if self.root == None:
            self.root = node
            return
        while cur:
            #向右側插入
            if item > cur.item:
                if cur.right == None:
                    cur.right = node
                    break
                else:
                    cur = cur.right

            else:#向左插入
                if cur.left == None:
                    cur.left = node
                    break
                else:
                    cur = cur.left
                    
    def middle(self,root):#中序:左根右
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
        
tree = SortTree()
alist = [3,8,5,7,6,2,9,4,1]
for i in alist:
    tree.add(i)
tree.middle(tree.root)  
# 執行結果
1
2
3
4
5
6
7
8
9

二分查找

# 一定是基于有序集合的查找
- 有序串列對于我們的實作搜索是很有用的，在順序查找中，當我們與第一個元素進行比較時，
如果第一個元素不是我們要查找的，則最多還有 n-1 個元素需要進行比較， 二分查找則是從中間元素開始，
而不是按順序查找串列， 如果該元素是我們正在尋找的元素，我們就完成了查找， 如果它不是，我們可以
使用串列的有序性質來消除剩余元素的一半，如果我們正在查找的元素大于中間元素，就可以消除中間元素
以及比中間元素小的一半元素，如果該元素在串列中，肯定在大的那半部分，然后我們可以用大的半部分重復該程序，
繼續從中間元素開始，將其與我們正在尋找的內容進行比較，

# 二分查找原理
- 隨便想一個1～100的數字，
你的目標是以最少的次數猜到這個數字，你每次猜測后，我會說小了、大了或對了，
從50 開始,小了，但排除了一半的數字！至此，你知道1～50都小了，接下來，你猜75，大了，那余下的數字又排除了一半！
使用二分查找時，你猜測的是中間的數字，從而每次都將余下的數字排除一半，

#  需要搜索的元素越多,二分查找的速度比普通遍歷查找就快得多，
#  二分查找O(log n) 比普通遍歷查找O(n)時間復雜度低，

# 代碼
def find(alist,item):
    find = False
    first = 0
    last = len(alist)-1
    
    while first <= last:
        mid_index = (first + last) // 2
        
        if alist[mid_index] < item:#去中間元素的右側繼續去尋找
            first = mid_index + 1
        elif alist[mid_index] > item:
            last = mid_index - 1
        else:
            find = True
            break
    return find,mid_index

alist = [1,2,3,4,5,6,7,8,9]
print(find(alist,1))
# 執行結果
True

冒泡排序

# 原理
- 比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
- 對每一對相鄰元素做同樣的作業，從開始第一對到結尾的最后一對，在這一點，最后的元素應該會是最大的數， 
- 針對所有的元素重復以上的步驟，除了最后一個， 
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，

# 代碼

#串列元素兩兩比較，大的值逐漸向后移動
def sort(alist):
    for i in range(len(alist)-1):
        if alist[i] > alist[i+1]:
            alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist
alist = [3,8,5,7,6]
print(sort(alist))
# 執行結果 [3, 5, 7, 6, 8]

# 逐漸將亂序序列的最大值找出放置在亂序序列的尾部
def sort(alist):
    for j in range(len(alist)-1):
        for i in range(len(alist)-1-j):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist

alist = [3,8,5,7,6]
print(sort(alist))   

# 執行結果 [3, 5, 6, 7, 8]

# 什么時候最快
當輸入的資料已經是正序時（都已經是正序了，我還要你冒泡排序有何用啊），

# 什么時候最慢
當輸入的資料是反序時（寫一個 for 回圈反序輸出資料不就行了，干嘛要用你冒泡排序呢，我是閑的嗎），

選擇排序

# 原理
- 選擇排序,可以理解為改進了冒泡排序，每次遍歷串列只做一次交換，為了做到這一點，一個選擇排序在他遍歷時尋找最大的值(最小值)，
并在完成遍歷后，將其放置在正確的位置(小的在前,大的在后)，直到所有元素均排序完畢，

# 代碼
# 將亂序中的最大值找出，跟最后一個元素交換位置
def sort(alist):
    max_index = 0 #最大值的下標
    for i in range(1,len(alist)):
        if alist[max_index] < alist[i]:
            max_index = i
    alist[len(alist)-1],alist[max_index] = alist[max_index],alist[len(alist)-1]
    return alist
# 執行結果 [3, 6, 5, 7, 8]

# 依次將亂序中的最大值找出，跟最后一個元素交換位置
def sort(alist):
    for j in range(0,len(alist)-1):
        max_index = 0 # 最大值的下標
        for i in range(1,len(alist)-j):
            if alist[max_index] < alist[i]:
                max_index = i
        alist[len(alist)-1-j],alist[max_index] = alist[max_index],alist[len(alist)-1-j]
    return alist

alist = [3,8,5,7,6]
print(sort(alist))
# 執行結果 [3, 5, 6, 7, 8]

# 選擇排序是一種簡單直觀的排序演算法，無論什么資料進去都是 O(n2) 的時間復雜度，所以用到它的時候，
資料規模越小越好，唯一的好處可能就是不占用額外的記憶體空間了吧，

插入排序

# 原理
將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列，從頭到尾依次掃描未排序序列，
將掃描到的每個元素插入有序序列的適當位置，（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面，）

# i有序子集中元素的個數,還可以表示下標
# alist[i]亂序子集中的第一個元素
# alist[i-1]有序子集中的最后一個元素

# 實作思路
i = 1 
if alist[i] < alist[i-1]:# 亂序子集中的第一個元素值小于有序子集中的最后一個元素的值,交換位置
    alist[i],alist[i-1] = alist[i-1],alist[i]
else:
    pass
i += 1

i = 2
while i > 0: # 有序子集個數大于0時,執行回圈 
    if alist[i] < alist[i-1]: 
        alist[i],alist[i-1] = alist[i-1],alist[i]
        i -= 1
    else:
        break
        
# 完整代碼
def sort(alist):
    for i in range(1,len(alist)): # 控制遍歷次數,(len(alist)-1)就可以完成排序
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]
                i -= 1
            else:
                break
    return alist

alist = [3,8,5,7,6]
print(sort(alist))

# 執行結果 [3, 5, 6, 7, 8]

希爾排序

希爾排序(Shell Sort)是插入排序的一種，也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本,
該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量（gap）”的元素組成的）
分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，
再對全體元素進行一次直接插入排序，因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，
因此希爾排序在時間效率比直接插入排序有較大提高，

希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本，但希爾排序是非穩定排序演算法，
- 希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
1.插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率；
2.但插入排序一般來說是低效的，因為插入排序每次只能將資料移動一位；
  希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，
待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序，    

# 代碼
def sort(alist):
    gap = len(alist)//2 #初始gap
    
    while gap >= 1:
        for i in range(gap,len(alist)):
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
                else:
                    break
        gap //= 2
    return alist
alist = [3,8,5,7,6]
print(sort(alist))
# 執行結果 [3, 5, 6, 7, 8]

快速排序

# 原理
1．先從數列中取出一個數作為基準數，
2．磁區程序，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊，
3．再對左右區間重復第二步，直到各區間只有一個數，

# 實作流程
    - 將串列中第一個元素設定為基準數字，賦值給mid變數，然后將整個串列中比基準小的數值放在基準的左側，
比基準到的數字放在基準右側，然后將基準數字左右兩側的序列在根據此方法進行排放，
    - 定義兩個指標，low指向最左側，high指向最右側
    - 然后對最右側指標進行向左移動，移動法則是，如果指標指向的數值比基準小，則將指標指向的數字移動到基準數字原始的位置，
否則繼續移動指標，
    - 如果最右側指標指向的數值移動到基準位置時，開始移動最左側指標，將其向右移動，如果該指標指向的數值大于基準則將該數值
移動到最右側指標指向的位置，然后停止移動，
    - 如果左右側指標重復則，將基準放入左右指標重復的位置，則基準左側為比其小的數值，右側為比其大的數值，

def sort(alist,start,end):
    #基數
    low = start
    high = end 
    
    if low > high:
        return
    
    mid = alist[start]
    while low < high:
        #偏移high
        while low < high:
            if alist[high] >= mid:
                #向左偏移high
                high -= 1
            else:
                alist[low] = alist[high]
                break
        #偏移low
        while low < high:
            if alist[low] <= mid:
                low += 1
            else:
                alist[high] = alist[low]
                break
        if low == high:
            alist[low] = mid
            break
    #作用到左側
    sort(alist,start,high-1)
    #左右到右側
    sort(alist,low+1,end)
    return alist

alist = [6,1,2,7,9,3,4,5,10,6,1,8]
print(sort(alist,0,len(alist)-1))

# 執行結果
[1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10]

標籤：Python

上一篇：跟哥一起學python（4）- 資料型別之Number

下一篇：numpy和matplotlib的學習筆記