算法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
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
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}
