算法基础
1、什么是算法？
算法（Algorithm）：一个计算过程，解决问题的方法
2、复习：递归
递归的两个特点：
两个重要递归函数的对比：
# 由大到小
def func3(x):
if x > 0 :
print(x)
func3(x-1)
# func3(5)
# 5 4 3 2 1
# 由小到大
def func4(x):
if x > 0 :
func4(x-1)
print(x)
func4(5)
# 1 2 3 4 5
3、时间复杂度
时间复杂度：用来评估算法运行效率的一个东西：
print('Hello World') # 0(1)
for i in range(n): # O(n)
print('Hello World')
for i in range(n): # O(n^2)
for j in range(n):
print('Hello World')
for i in range(n): # O(n^3)
for j in range(n):
for k in range(n):
print('Hello World')
第一个打印了一次时间复杂度为O(1)；第二个打印了n次，所以时间复杂度为O(n);第三四个依次为n²和n的3次方
那么看看下面代码中的时间复杂度为多少?
# 非O(3) 而是O(1)
print('Hello World')
print('Hello Python')
print('Hello Algorithm')
# 非O(n²+n) 而是O(n²)
for i in range(n):
print('Hello World')
for j in range(n):
print('Hello World')
# 非O(1/2n²) 而是O(n2)
for i in range(n):
for j in range(i):
print('Hello World')
再看看下面代码：
# 时间复杂度 O(log2n) 或 O(logn)
while n > 1:
print(n)
n = n // 2
# n=64输出：
# 64
# 32
# 16
# 8
# 4
# 2
小结：
时间复杂度是用来估计算法运行时间的一个式子（单位）。
一般来说，时间复杂度低的算法比复杂度低的算法快。
常见的时间复杂度（按用时排序）
- O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
不常见的时间复杂度（看看就好）
如何一眼判断时间复杂度？
- 循环减半的过程?O(logn)
- 几次循环就是n的几次方的复杂度
4、空间复杂度
空间复杂度：用来评估算法内存占用大小的一个式子
列表查找
列表查找：从列表中查找指定元素
- 输入：列表、待查找元素
- 输出：元素下标或未查找到元素
1、顺序查找
从列表第一个元素开始，顺序进行搜索，直到找到为止
def linear_search(data_set, value):
for i in data_set:
if data_set[i] == value:
return i
return
时间复杂度为O(n)
2、二分查找
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半
# 正宗的二分查找
data = [i for i in range(9000000)]
import time
def cal_time(func):
def inner(*args,**kwargs):
t1 = time.time()
re = func(*args,**kwargs)
t2 = time.time()
print('Time cost:',func.__name__,t2-t1)
return re
return inner
@cal_time
def bin_search(data_set,val):
low = 0
high = len(data_set) - 1
while low <= high:
mid = (low + high)//2
if data_set[mid] == val:
return mid
elif data_set[mid] < val:
low = mid +1
else:
high = mid -1
bin_search(data, 999)
# Time cost: bin_search 0.0005002021789550781
时间复杂度为O(logn),运行后会发现执行的很快，下面对比下之前Alex讲过的二分查找
# Alex的low版本
data = [i for i in range(9000000)]
import time
def cal_time(func):
def inner(*args,**kwargs):
t1 = time.time()
re = func(*args,**kwargs)
t2 = time.time()
print('Time cost:',func.__name__,t2-t1)
return re
return inner
def _binary_search(dataset, find_num):
if len(dataset) > 1:
mid = int(len(dataset) / 2)
if dataset[mid] == find_num: # find it
print("找到数字", dataset[mid])
elif dataset[mid] > find_num: # 找的数在mid左面
return _binary_search(dataset[0:mid], find_num)
else: # 找的数在mid右面
return _binary_search(dataset[mid + 1:], find_num)
@cal_time
def binary_search(dataset, find_num):
_binary_search(dataset, find_num)
binary_search(data, 999)
# Time cost: binary_search 0.4435563087463379
3、练习
现有一个学员信息列表（按id增序排列），格式为：
[
{id:1001, name:"张三", age:20},
{id:1002, name:"李四", age:25},
{id:1004, name:"王五", age:23},
{id:1007, name:"赵六", age:33}
]
修改二分查找代码，输入学生id，输出该学生在列表中的下标，并输出完整学生信息
import random
import time
# 生成随机列表
def random_list(n):
result = []
ids = list(range(1001,1001+n))
n1 = ['赵','王','孙','李']
n2 = ['国','爱','清','菲','']
n3 = ['甄','轩','雨','军']
for i in range(n)