算法基础
一、什么是算法？
算法（Algorithm）:一个计算过程，解决问题的方法。
）
(1)时间复杂度
时间复杂度：用来评估算法运行效率的一个东西
print('Hello World') O(1) for i in range(n): print('Hello World') O(n) for i in range(n): for j in range(n): print('Hello World') O(n2) for i in range(n): for j in range(n): for k in range(n): print('Hello World') O(n3)
小结
(2)空间复杂度
空间复杂度：用来评估算法内存占用大小的一个式子
二、算法事例
1.二分查找
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
es:使用二分查找来查找3
def bin_search(data,val): low =0 #左边的第一个位置 high = len(data) -1 #最右边的位置 while low <= high: mid =(low +high)//2 #中间的位置 if data[mid] == val: #表示中间的位置找到 return mid #返回下标 elif data[mid] >val: high =mid-1 else: low =mid +1 return #没找到就是返回 none
时间复杂度：O(logn)
2.冒泡排序
首先，列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数……
def bubble(li): for i in range(len(li)-1): #执行趟数 for j in range(len(li) - i-1): #执行每趟时要交换的次数 if li[j]>li[j+1]: #前面的一个数比后面的一个数大 li[j],li[j+1]=li[j+1],li[j] # 进行位置交换
时间复杂度 ： O(n2)
如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法。
2.冒泡排序
思路：一趟遍历记录最小的数，放到第一个位置；
再一趟遍历记录剩余列表中最小的数，继续放置；
def select_sort(li): for i in range(len(li)): #要执行的趟数 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] #交换
时间复杂度： O(n2)
3.插入排序
思路：
列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
*****************抓牌，插牌***********
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 = j-1 #往左进行比较 li[j+1] =tmp #无序区取到的牌比有序区的牌都大
时间复杂度： O(n2)