算法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
# 900003、二分查找实例
通过二分查找，输入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}
