算法Algorithm

一个计算过程，解决问题的方法

递归：

• 调用自身
• 结束条件

时间复杂度：

• 用来估计算法运行时间的一个式子
  O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n2logn) < O(n^3)

• 一般来说，时间复杂度高的算法比复杂度低的算法慢

• 不常见的时间复杂度：
  O(n!) O(2^n) O(n^n)

时间复杂度判断

• 循环减半的过程 -> O(logn)
• 几次循环就是n的几次方

空间复杂度：

• 用来评估算法内存占用大小的式子

空间换时间

列表查找

• 从列表中查找指定元素
• 输入：列表，待查元素
• 输出：元素下标或未查找到元素

顺序查找：

• 从列表第一个元素开始，顺序进行搜索，直到找到为止

二分查找：

• 从有序列表的候选区data[0: n]开始，通过对待查找的值与候选区中间的值比较，可以使候选区减少一半

代码实例

1、递归

#先打印再调用
def foo1(x): if x > 0: print(x) foo1(x-1)

foo1(5)
# 5 4 3 2 1

# 先调用再打印
def foo2(x): if x > 0: foo2(x-1) print(x)

foo2(5)
# 1 2 3 4 5
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

2、顺序查找与二分查找

# -*- coding: utf-8 -*-

import time

# 计时装饰器
def timer(func): def wrapper(*args, **kwargs): start = time.time() ret = func(*args, **kwargs) end = time.time() print("time: %s"% (end-start)) return ret return wrapper
# 顺序（线性）查找 O(n)
@timer
def line_search(lst, val): for index, value in enumerate(lst): if val == value: return index return None

# 二分查找(需要有序) O(logn)
@timer
def binary_search(lst, val): low = 0 high = len(lst) - 1 while low <= high: mid = (high + low)//2 if lst[mid] == val: return mid elif lst[mid] < val: low = mid + 1 else: high = mid - 1 return None
if __name__ == '__main__': lst = list(range(100000)) ret = line_search(lst, 90000) print(ret) # time: 0.007 # 90000 ret = binary_search(lst, 90000) print(ret) # time: 0.000 # 90000

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
 

3、二分查找实例

• 通过二分查找，输入id 查找学生完整信息

# -*- coding: utf-8 -*-

import random
from chinesename import chinesename  # pip install chinesename

# 二分查找函数
def binary_search(lst, uid): low = 0 high = len(lst) - 1 while low <= high: mid = (low + high)//2 if lst[mid]["uid"] == uid: return lst[mid] elif lst[mid]["uid"] < uid: low = mid + 1 else: high = mid - 1 return None

# 生成学生信息
def get_students(n): """ @param n: 数量 @return: {list} """ cn = chinesename.ChineseName() uids = list(range(1001, 1001+n)) lst = [] for uid in uids: dct = { "uid": uid, "name": cn.getName(), "age": random.randint(18, 60) } lst.append(dct) return lst
if __name__ == '__main__': students = get_students(100000) ret = binary_search(students, 1005) print(ret) # {'uid': 1005, 'name': '相佃', 'age': 58}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

文章来源: pengshiyu.blog.csdn.net，作者：彭世瑜，版权归原作者所有，如需转载，请联系作者。

原文链接：pengshiyu.blog.csdn.net/article/details/80602717