程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

[Algorithm] 1. Sequential search (with Python code)

編輯:Python

文章目錄

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

活動地址: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.

1. 算法基本概念

1.1 算法的定義

英語: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

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 元素查找介紹

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,可以理解為一維數組.

常見的查找算法:

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

2.2 順序查找

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)

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved