什么是算法
就是一个计算的过程，解决问题的方法
用到知识点
递归
调用自身
有结束条件
下次执行相应的复杂度要减少
时间复杂度排序（按效率排序）
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
判断时间复杂度
1.循环减半的过程就是O(logn)
2.几次循环就是n的几次方的复杂度
空间复杂度(以空间换时间)
评估算法内存占用大小
列表查找
顺序查找
从列表第一个元素开始，顺序进行搜索，直到找到为止。
def linear_seach(data_set,val): for i in range(5,data_set): if i == val: print(i) return i return '没找到'
二分查找
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
def bin_seacher(data_set,val): low = 0 high = len(data_set) - 1 while low <= high: mid = (low+high) // 2 if data_set[mid] == val: print('索引位置：',mid) return mid elif data_set[mid] < val: low = mid + 1 else: high = mid - 1 print('没有找到') return None li = range(100000) bin_seacher(li,557)
案例
import random def random_list(n): ''' 生成随机数据 :param n: :return: ''' ret = [] a1 = ['赵','钱','孙','李','邹','吴','郑','王','周'] a2 = ['力','好','礼','丽','文','建','梅','美','高',''] a3 = ['强','文','斌','阔','文','莹','超','云','龙',''] ids = range(1001,1001+n) for i in range(n): name = random.choice(a1) + random.choice(a2) +random.choice(a3) age = random.randint(18,60) dic = {'id':ids[i], 'name':name, 'age':age} ret.append(dic) return ret def id_seacher(data_list,id): low = 0 high = len(data_list) - 1 while low <= high: mid = (low+high) // 2 if data_list[mid]['id'] == id: print('索引位置：',mid) return mid elif data_list[mid]['id'] < id: low = mid + 1 else: high = mid - 1 print('没有找到') return None data_list = random_list(100) ind = id_seacher(data_list,1025) print(data_list[ind]['name'])#输入人名
冒泡排序
首先，列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数
循环无序区的数继续比较
import random def bubble_sort(li): for i in range(len(li) - 1):# 几趟 exchange = False # 标志位 for j in range(len(li) - i - 1): if li[j] > li[j + 1]: li[j], li[j + 1] = li[j + 1], li[j] exchange = True if not exchange: break li = list(range(1000)) random.shuffle(li) print(li) bubble_sort(li) print(li)
时间复杂
最好情况 O（n）
一般情况 O (n2)
最差情况 O (n2)
选择排序
一趟遍历记录最小的数，放到第一个位置；
再一趟遍历记录剩余列表中最小的数，继续放置；
def select_sort(li): for i in range(len(li) - 1): #循环次数 min_loc = i for j in range(i + 1,len(li)):#从无序区找 if li[j] < li[min_loc]: min_loc = j li[i], li[min_loc] = li[min_loc], li[i] li = list(range(1000)) random.shuffle(li) print(li) select_sort(li) print(li)
插入排序
列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
def insert_sort(li): for i in range(1,len(li)): tmp = li[i] j = i - 1 while j >= 0 and tmp < li[j]: # 判断新数是否比前一个数小，小就将前一个数向后挪一个位置 li[j + 1] = li[j] j -= 1 li[j + 1] = tmp li = list(range(1000)) random.shuffle(li) print(li) insert_sort(li) print(li)
a. 时间效率
# coding:utf-8 from timeit import Timer # li1 = [1, 2] # # li2 = [23,5] # # li = li1+li2 # # li = [i for i in range(10000)] # # li = list(range(10000)) def t1(): li = [] for i in range(10000): li.append(i) def t2(): li = [] for i in range(10000): li += [i] def t3(): li = [i for i in range(10000)] def t4(): li = list(range(10000)) def t5(): li = [] for i in range(10000): li.extend([i]) timer1 = Timer("t1()", "from __main__ import t1") print("append:", timer1.timeit(1000)) timer2 = Timer("t2()", "from __main__ import t2") print("+:", timer2.timeit(1000)) timer3 = Timer("t3()", "from __main__ import t3") print("[i for i in range]:", timer3.timeit(1000)) timer4 = Timer("t4()", "from __main__ import t4") print("list(range()):", timer4.timeit(1000)) timer5 = Timer("t5()", "from __main__ import t5") print("extend:", timer5.timeit(1000)) def t6(): li = [] for i in range(10000): li.append(i) def t7(): li = [] for i in range(10000): li.insert(0, i) #------------------结果------- append: 1.0916136799496599 +: 1.0893132810015231 [i for i in range]: 0.4821193260140717 list(range()): 0.2702883669990115 extend: 1.576017125044018
def t6(): li = [] for i in range(10000): li.append(i) def t7(): li = [] for i in range(10000): li.insert(0, i) timer6 = Timer("t6()", "from __main__ import t6") print("append", timer6.timeit(1000)) timer7 = Timer("t7()", "from __main__ import t7") print("insert(0)", timer7.timeit(1000)) #################### append 1.1599015080137178 insert(0) 23.26370093098376