文章目錄

• 1. 算法基本概念
• • 1.1 算法的定義
  • 1.2 算法的效率
• 2. 順序查找
• • 2.1 元素查找介紹
  • 2.2 順序查找

活動地址：CSDN21天學習挑戰賽

學而不思則罔，思而不學則殆。
本人自學算法有一小段時間了，但一直沒做什麼筆記和總結，學習內容也不成體系。借這個活動的機會，和大家一起學習、梳理一下經典算法。

1. 算法基本概念

1.1 算法的定義

英語：algorithm，在數學（算學）和計算機科學之中，指一個被定義好的、計算機可施行其指示的有限步驟或次序，常用於計算、數據處理和自動推理。算法是有效方法，包含一系列定義清晰的指令，並可於有限的時間及空間內清楚的表述出來。
– 維基百科

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.
– Introduction to Algorithms

1.2 算法的效率

算法的效率主要由以下兩個復雜度來評估：
時間復雜度：評估執行程序所需的時間。可以估算出程序對處理器的使用程度。
常見的時間復雜度有（由低到高）： O ( 1 ) , O ( log ⁡ 2 n ) , O ( n ) , O ( n log ⁡ 2 n ) , O ( n 2 ) , O ( n 3 ) ,  O ( 2 n ) ,  O ( n ! ) \mathrm{O}(1), \mathrm{O}\left(\log _{2} n\right), \mathrm{O}(\mathrm{n}), \mathrm{O}\left(n \log _{2} n\right), \mathrm{O}\left(n^{2}\right), \mathrm{O}\left(n^{3}\right) \text {, }\mathrm{O}\left(2^{n})\text {, }\right.O(n !) O(1),O(log2​n),O(n),O(nlog2​n),O(n2),O(n3), O(2n), O(n!)

空間復雜度：評估執行程序所需的存儲空間。可以估算出程序對計算機內存的使用程度。

設計算法時，一般是要先考慮系統環境，然後權衡時間復雜度和空間復雜度，選取一個平衡點。不過，時間復雜度要比空間復雜度更容易產生問題，因此算法研究的主要也是時間復雜度，不特別說明的情況下，復雜度就是指時間復雜度。

2. 順序查找

2.1 元素查找介紹

查找也被稱為檢索，算法的主要目的是在某種數據結構中找出滿足給定條件的元素（以等值匹配為例）。如果找到滿足條件的元素則代表查找成功，否則查找失敗。
在進行查找時，對於不同的數據結構以及元素集合狀態，會有相對匹配的算法，在使用時也需要注意算法的前置條件。在元素查找相關文章中只討論數據元素只有一個數據項的情況，即關鍵字（key）就是對應數據元素的值，對應到具體的數據結構，可以理解為一維數組。

常見的查找算法：

• 順序查找
• 二分查找
• 索引查找

2.2 順序查找

順序查找理論介紹
時間復雜度：O(n)
空間復雜度：O(1)

Python 代碼實現

from typing import List
def search(nums: List[int], key: int) -> int:
n = len(nums)
for i in range(n):
if nums[i] == key:
return i
return -1
if __name__ == '__main__':
A = [11, 34, 20, 10, 12, 35, 41, 32, 43, 14]
key = 41
ans = search(A, key)
print(ans)