一、时间复杂度
1.用来评估算法运行效率的一个东西。
2.一般来说，时间复杂度高的算法比复杂度低的算法慢
3.常见的时间复杂度（效率排序)
o(1)<o(logn)<o(n)<o(nlogn)<o(n^2)<o(n^ 2logn)<o(o^3)
4.不常见的时间复杂度
o(n!)/o(2^n)/o(n^n)
5.如何一眼判断时间复杂度？
-循环的过程中出现了循环减半-----o(logn)
-几次n的循环就是n的几次方的复杂度
二、空间复杂度
1.空间复杂度：用来评估算法内存占用大小的一个式子
2."空间换时间"
三、递归
1、递归的两个特点:
-调用自身
-有结束条件
四、列表查找
1.列表查找：从列表中查找指定元素
-输入：列表、待查找元素。->无序列表
-输出：元素下标或未查找到元素。有序列表
2.顺序查找
-从列表第一个元素开始，顺序进行搜索，知道找到为止
3.二分查找
-从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。"""
顺序查找 """
li = list(range(0,1000,2)) def linear_search(li,value): try:
i =li.index(val)
return i
except:
return None
""" 二分查找 """ def bin_search(li,value): low =0 high = len(li)-1 while low <=high: mid = (low+high)//2 if data_set[mid] == value: return mid elif data_set[mid] > value: high = mid-1 else: low = mid+1
else:
return None
""" 二分查找-递归 """ def bin_search_rec(data_set,value,low,high): if low<=high: mid = (low+high)//2 if data_set[mid]==value: return mid elif data_set[mid]>value: return bin_search_rec(data_set,value,low,mid-1) else: return bin_search_rec(data_set,value,mid+1,high) else: return
4.汉诺塔问题
def hanota(n,a,b,c): if n>0: hanota(n-1,a,c,b) print("#%d:moving from %s to %s"%(num,a,c)) hanota(n-1,b,a,c) """ 当有n个盘子时： 1.把n-1个圆盘从A经过C移动到B 2.把第n个圆盘从A移动到C 3.把n-1个小圆盘从B经过A移动到C 汉诺塔移动次数的递归式：h(x) = 2h(x-1)+1 """
五、排序方法
1.冒泡排序
def bubble_sort(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(n^2) """ 优化 """ def bubble_sort_1(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: return
2.选择排序
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 if min_loc ! =i: li[i],li[min_loc]=li[min_loc],li[i] #时间复杂度：o(n^2)
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(n^2)
4.快速排序
""" -取一个元素p（第一个元素），使元素p归位； -列表被p分为两部分，左边都比p小，右边都比p大； -递归完成排序 """ def quick_sort(data,left,right): if left < right: mid = partition(data,left,right) quick_sort(data,left,mid-1) quick_sort(data,mid+1,right) def partiton(data,left,right): tmp = data[left] while left<right: while left<right and data[right] >=tmp: right-=1 data[left] = data[right] while left <right and data[left]<=tmp: left+=1 data[right] = data[left] data[left] = tmp return left
5.堆排序
""" 1.建立堆 2.得到堆顶元素，为最大元素 3.去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一个次 调整重新使堆有序 4.堆顶元素为第二大元素 5.重复步骤3，知道堆变空 """ def sift(data,low,high): i =low j = 2*2+1 while j<=high: if j<high and data[j]<data[j+1]: j+=1 if tmp < data[j]: data[i] = data[j] i =j j = 2*i+1 else: break data[i] =tmp def heap_sort(data): n = len(data) for i in range(n//2-1,-1,-1): sift(data,i,n-1) for i in range(n-1,-1,-1): data[0],data[i] = data[i],data[0] sift(data,0,i-1)
#python内置排序--heapq
-heapify(x)
-heappush(heap,item)
-heappop(heap)
优先队列：一些元素的集合，pop操作每次执行都会从优先队列中弹出最大（或最小）的元素
堆---优先队列
#利用heapq模块实现堆排序 def heapsort(li): h=[] for value in li: heappush(h,value) return [heappop(h) for i in range(len(h))]
#Top-k问题
#现在有n个数，设计算法找出前k大的数（k<n） """ 解决思路 -取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数。 -依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整。 -遍历列表所有元素后，倒序弹出堆顶。 """ def topk(li,k): heap = li[0:k] for i in range(k//2-1,-1,-1): sift(heap,i,k-1) for i in range(k,len(li)): heap[0] = li[i] sift(heap,0,k-1) for i in range(k-1,-1,-1): heap[0],heap[i] = heap[i],heap[0] sift(heap,0,i-1)
6.归并排序
def merge(li,low,mid,high): i =low j = mid+1 ltmp = [] while i <=mid and j <=high: if li[i]<=li[j]: ltmp.append(li[i]) i+=1 else: ltmp.append(li[j]) j+=1 while i <=mid: ltmp.append(li[i]) i+=1 while j<=high: ltmp.append(li[j]) j+=1 li[low:high+1] = ltmp ################################# def mergesort(li,low,high): if low<high: mid = (low+high)//2 mergesort(li,low,mid) mergesort(li,mid+1,high) merge(li,low,mid,high) """ 时间复杂度：O(nlogn) 空间复杂度：O(n) """