活動地址:CSDN21天學習挑戰賽
學而不思則罔,思而不學則殆.
I have been teaching myself algorithms for a while,But I haven't made any notes and summaries,The learning content is also not systematic.Take the opportunity of this event,和大家一起學習、Check out the classic algorithm.
英語:algorithm,在數學(算學)和計算機科學之中,指一個被定義好的、The computer can perform the limited steps or sequences it instructs,常用於計算、數據處理和自動推理.Algorithms are efficient,包含一系列定義清晰的指令,並可於有限的時間及空間內清楚的表述出來.
– 維基百科
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
算法的效率主要由以下兩個復雜度來評估:
時間復雜度:評估執行程序所需的時間.可以估算出程序對處理器的使用程度.
常見的時間復雜度有(由低到高): 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(log2n),O(n),O(nlog2n),O(n2),O(n3), O(2n), O(n!)
空間復雜度:評估執行程序所需的存儲空間.可以估算出程序對計算機內存的使用程度.
設計算法時,一般是要先考慮系統環境,然後權衡時間復雜度和空間復雜度,選取一個平衡點.不過,時間復雜度要比空間復雜度更容易產生問題,因此算法研究的主要也是時間復雜度,不特別說明的情況下,復雜度就是指時間復雜度.
A lookup is also called a retrieval,The main purpose of an algorithm is to find elements in a certain data structure that satisfy a given condition(Take equality matching as an example).If an element that satisfies the condition is found, the search is successful,否則查找失敗.
在進行查找時,For different data structures and element collection states,There will be relatively matching algorithms,It is also necessary to pay attention to the preconditions of the algorithm when using it.Only the case where the data element has only one data item is discussed in the element lookup related article,即關鍵字(key)is the value of the corresponding data element,corresponds to a specific data structure,可以理解為一維數組.
常見的查找算法:
An introduction to sequential search theory
時間復雜度: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)