大 O 表示法

大 O 表示法在討論運行時間時，log 指的都是 log₂

大 O 表示法指出了算法有多快，讓你能夠比較操作數，它指出了算法運行時間的增速，而并非以秒為單位的速度。

大 O 表示法指出了最糟情況下的運行時間。

下面按從快到慢的順序列出了經常會遇到的5種大O運行時間：

• O(log n)，也叫對數時間，這樣的算法包括二分查找
• O(n)，也叫線性時間，這樣的算法包括簡單查找
• O(n * log n)，這樣的算法包括快速排序 —— 一種速度較快的排序算法
• O(n²)，這樣的算法包括選擇排序 —— 一種速度較慢的排序算法
• O(n!)，這樣的算法包括旅行商問題的解決方案 —— 一種非常慢的算法

1. O(1)

時間復雜度，比如操作一步到位這是常數級別的時間復雜，即為 O(1)。

a = 100 / 2 + 101 * 10 + 5 

3. O(logn)

如下操作，每次 n 會被除以 3，遍歷次數等于 以 3 為底 log n 次。在大 O 標記體系中，以 3 為底和以 5 為底沒有區別，所以統一標記為 O(logn)。

def f(n):while n > 0:print(n)n //= 3

4. o(n)

線型復雜度也是很理想的情況，如下面的操作，每次遍歷，n 減去 3，這樣總共遍歷(n-1)/3 + 1 次后算法終止，根據大 O 標記法，算法的時間復雜為 O(n)。

def f(n):while n > 0:print(n)n -= 3

5. O(nlogn)

如下面所示的兩層循環，復雜度便是 nlogn。外層循環的運行次數為 n，里層循環的運行次數為 logn 次，所以一共需要 nlogn 次。

def f(n):for i in range(n):for j in range(1,n,2):print(i*j)

6. O(n^2)

O(n^2) 是多項式時間復雜度的代表，此類算法的時間復雜度已經難以劃分到高效算法集合中，它只能是問題的有效解，而不是高效解。如下兩層 for 循環，時間復雜度就是 O(n^2)。

def f(n):for i in range(n):for j in range(n):print(i*j)

7. O(2^n)

時間復雜度為 O(2^n) 的算法是指數級增長的，此類復雜度下求解的問題往往都是難題，因為隨著問題規模 n 的增長，指數級的增長速度是驚人的。

例如經典的旅行商問題，商人要去 n 個地方拜訪，如何規劃拜訪順序才能使得旅行距離最短。如果僅拜訪肉眼可見的兩三個地方時，我們還能窮舉所有拜訪的組合，進而找到最短路徑。

但是當問題規模 n 變大時，目前所有的計算機資源總和都難以在有限的時間里計算出最優的最短路徑，這類問題的時間復雜度都為指數級，屬于 NP 難問題。

二分查找與簡單查找

二分查找的輸入必須為有序的元素列表，查找的時候每次獲取中間的元素。

簡單查找則是按照順序從頭至尾的查找每個元素。

一般而言，對于包含n個元素的列表，用二分查找最多需要 log₂n 步，而簡單查找最多需要n步。

二分查找算法代碼如下：

def binary_search(arr, num):arr.sort()  # 對輸入參數先進行排序print arrlow = 0high = len(arr) - 1while low <= high:	# 通過下表縮小范圍mid = (low + high)/2if arr[mid] < num:low = mid + 1elif arr[mid] > num:high = mid - 1elif arr[mid] == num:return midelse:return "Not Exists"a = [10, 2, 8, 1, 3, 20, 15]
print binary_search(a, 10)
#打印值
[1, 2, 3, 8, 10, 15, 20]
4

選擇排序

選擇排序的思路大概分為兩步：

1. 對要排序的 N 個元素依次進行比較，返回要獲取的最大值或者最小值；

2. 將返回的最大值或者最小值添加到新的列表中，在原列表中刪除該元素，并繼續重復步驟 a，直到原列表中沒有元素；

選擇排序代碼：

def find_min(arr):  # 找出最小值min_value = arr[0]index = 1while index <= len(arr) - 1:if arr[index] < min_value:min_value = arr[index]index += 1return min_valuedef select_sort(arr):   # 將找到的最小值依次在原列表中刪除，并存入新列表dst = []for i in range(len(arr)):min_value = find_min(arr)dst.append(min_value)arr.remove(min_value)return "dst is {0}".format(dst)a = [10, 2, 8, 30, 3, 20, 15]
print select_sort(a)
# 輸出
dst is [2, 3, 8, 10, 15, 20, 30]

遞歸算法

每個遞歸函數都分為兩部分：基線條件和遞歸條件。

基線條件是指函數的終止條件，即避免形成死循環的部分；遞歸條件則指的是函數自己調用自己。

計算階乘的遞歸函數

def fact(x):if x == 1:return 1else:return x * fact(x-1)print fact(5)

計算斐波那契數列某一項的值

def fibo(n):if n == 0 or n == 1:return nelse:return fibo(n-1) + fibo(n-2)print fibo(7)

快速排序算法

快速排序比選擇排序的算法快很多，它可借助遞歸方法實現，主要步驟如下：

1. 選擇基準值；

2. 將待排序的數組分成兩個子數組：小于基準值的元素和大于基準值的元素；

3. 分別在對這兩個子數組進行快速排序；

def quick_sort(array):if len(array) < 2:  # 為空或者只包含一個元素時return arrayelse:base = array[0]     # 基準值less = [x for x in array[1:] if x <= base]      # 所有小于基準值的元素greater = [y for y in array[1:] if y > base]    # 所有大于基準值的元素return quick_sort(less) + [base] + quick_sort(greater)  # 對兩組數據進行遞歸排序a = [10, 2, 8, 30, 3, 20, 15]print quick_sort(a)

散列表

散列表也被稱為散列映射、映射、字典和關聯數組等。在 python 語言中表現為字典形式，要求將同樣的輸入映射到相同的索引，將不同的輸入映射到不同的索引。可將字典用于查找、服務器緩存等場景。

散列表的查找、插入和刪除速度都非常快，散列表適合用于模擬映射關系以及用于防止重復。

廣度優先搜素

從 A 到 B 地有很多種路徑可以到達，但是只有一條路徑是最短路徑，這種尋找最短、最優路徑問題被稱為最短路徑問題。

解決最短路徑問題的算法被稱為廣度優先搜索。

圖由節點和邊組成，一個節點可能與眾多節點直接相連，這些節點被稱為鄰居。

廣度優先搜索是一種用于圖的查找算法，可解決兩類問題：

1. 從節點A出發，有前往節點B的路徑嗎？

2. 從節點A出發，前往節點B的哪條路徑最短？

有向圖與無向圖的區別：

• 有向圖中的邊為箭頭，箭頭的方向指定了關系的方向；

• 無向圖中的邊不帶箭頭，其中的關系是雙向的；

廣度優先搜索的運行時間為O(人數 + 邊數)，這通常寫作O(V + E)，其中V為頂點（vertice）數，E為邊數。

總結

以上是生活随笔為你收集整理的算法图解/二分查找/简单查找/选择排序/递归算法/快速排序算法/的全部內容，希望文章能夠幫你解決所遇到的問題。

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