本文共 9162 字，大约阅读时间需要 30 分钟。

一.时间复杂度

时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。

• 常数阶$O(1)$
• 线性阶$O(n)$
• 平方阶$O(n^2)$
• 立方阶$O(n^3)$
• 对数阶$O(logn)$
• 线性对数阶$O(nlogn)$
• 指数阶$O(2^n)$

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

---

二.空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

常数：o(1)

一维数组:o(n)

二维数组:o(n+m)

---

三.递归

递归，就是在运行的过程中调用自己。

构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

def h(n):    if n>0:        print(n)        h(n-1)h(3)结果：3,2,1先打印后递归def h(n):    if n>0:        h(n-1)        print(n)h(3)结果：1,2,3先递归后打印

---

四.汉诺塔

第一步：把a经过b移到c

第二步:把a移到c 第三步：把b经过a移到c 递推公式：h(x)=2h(x-1)+1

def h(n,a,b,c):    if n>0:        h(n-1,a,c,b)        print('把%s移动到%s'% (a,c))        h(n-1,b,a,c)h(3,'A','B','C')

---

五.斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列

F[n]=F[n-1]+F[n-2] (n>=2,F[0]=0,F[1]=1)

第一种：

def fib_recur(n):   assert n >= 0, "n > 0" 	if n <= 1:   	return n 	return fib_recur(n-1) + fib_recur(n-2)for i in range(1, 20):   print(fib_recur(i), end=' ')

第二种：

def fib_loop_for(n):  	a, b = 0, 1  	for _ in range(n):    	a, b = b, a + b    return adef fib_loop_while(n):  	a, b = 1, 1  	while n > 0:    	a, b = b, a + b    	n -= 1  	return afor i in range(20):  	print(fib_loop_for(i), end=' ')

斐波那契数列的应用题：

1 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。

提示：f(n) = f(n-1) + f(n-2)

扩展题：

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶…也可以跳上n级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。

提示：f(n) = 2n-1

2 如果我们用21的小矩形横着或者竖着去覆盖更大的矩形。请问8个21的小矩形无重叠地覆盖一个2*8的大矩形，总共有多少种方法？

提示：f(8) = f(7) + f(6)

---

线性查找

在常规无序数组中

，设数组项个数为N，则一个数组项平均查找长度为N/2。极端情况下，查找数据项在数组最后，则需要N步才能找到。

def line_search(li,val):	for k,v in enumerate(li):		if v ==val:			return k	else:		return None

---

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

def bindary_search(li,val):	left = 0	right = len(li)-1	while left <= right:		mid = (left + mid)//2		if li[mid] ==val:			return mid		elif li[mid] > val:			right = mid -1		elif li[mid]

---

冒泡排序

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

• 针对所有的元素重复以上的步骤，除了最后一个。

• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bullue_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]

改进：

def bullue_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]				exchange = True			if not exchange:				return

排序次数：n(n-1)/2

---

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾

def select_sort_one(li):	li_new=[]	for i in range(len(li)-1): #第几躺		min_num = min(li)		li_new.append(min_num)		li.remove(min_num)	return li_new

改进

def select_sort_advance(li):	for i in range(len(li)-1):		min_num = i		for j in range(i+1,len(li)):			if li[j] < li[min_num]:				min_num = j		if min_num != i:			li[i],li[min_num] = li[min_num],li[i]

---

插入排序

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，

现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数

的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的

过程，称为插入排序 。

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的

牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找

到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的

牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌 。

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

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R.Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

def partation(li,left,right):	tem = li[left]	while left < right:		while left
   
    = tmp:			right -=1			li[left] = li[rigth]		while left < right and li[left] <= tmp:			left +=1			li[right] = li[left]	li[left] = tmp	return left
   

def quick(li,left,right):	if left < right:		mid = partation(li,left,right)		quick(li,left,mid-1)		quick(li,mid+1,right)quick(li,0,len(li)-1)

堆排序

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

• 高度：有几层就是几
• 度 ：分支最大数

满二叉树：

国际标准定义是除了叶结点外每一个结点都有左右子结点的二叉树

完全二叉树：

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。

父亲节点和左孩子关系：2i+1

父亲节点和右孩子：2i+2

堆：一种特殊二叉树

大根堆，小根堆

堆的向下调整：

大的往上调，小的往下调

归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

def mergre(li,low,mid,hight):	i=low	j=mid+1	ltep =[]	while i<=mid and j <= hight:		if li[i]

def merge_sort(li,low,hight):	if low

总结

希尔排序

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。

希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

def insert_sort_grap(li,gap):	for i in range(gap,len(li)):		tmp=li[i]		j = i - gap		while j>=0 and li[j]>tmp:			li[j+gap] =li[j]			j -= gap		li[j+gap] = tmp

def short_sort(li):	d = len(li) // 2	while d >= 1:		insert_sort_grap(li,d)		d //= 2

计数排序

计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

def count_sort(li,max_count=100):	count=[0 for_in range(max_count+1)]	for val in li:		count[val] +=1	li.clear()	for ind,val in enunerate(count):		for i in range(val):			li.append(ind)

桶排序

桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

def bukcer_sort(li,n=100,max_num=1000):	buckets=[[] for _ in range(n)]	for var in li:		i = min(var //(max_num // n),n-1)		buckets[i].append(var)		for j in range(len(buckets[i])-1,0,-1):			if buckets[i][j] < buckets[i][j-1]:				buckets[i][j-1] = buckets[j-1][i]			else:				break	sort_li =[]	for buc in backets:		sort_li.extend(buc)	return sort_li

基数排序

基数排序(Radix Sort)是在桶排序的基础上发展而来的，两种排序都是分配排序的高级实现。分配排序(Distributive Sort)的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

def radix_sort(li):	max_num =max(li)	it = 0	while 10 ** it <= max_num:		buckets=[[] for _ in range(10)]		for var in li:			digit = (var //10 ** it) % 10			buckets[digit].append(var)		li.clear()		for buc in buckets:			li.extend(buc)		it +=1

栈：

栈就是先进后出

class stack:	def __init__(self):		self.stack=[]	def push(self,item):		self.stack.append(item)	def pop(self):		return self.stack.pop()

队列

队列就是先进先出

class Queue():d	def __init__(self):		self.items=[]	def enqueue(self,item):		self.items.insert(0,item)	def dequeue(self):		self.items.pop()

输出/删除 单链表倒数第 K 个节点

class Solution:    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:        second = fist = head        for i in range(n):  # 第一个指针先走 n 步            fist = fist.next         if fist == None:  # 如果现在第一个指针已经到头了，那么第一个结点就是要删除的结点。            return second.next         while fist.next:  # 然后同时走，直到第一个指针走到头            fist = fist.next            second = second.next        second.next = second.next.next  # 删除相应的结点        return head

删除链表中节点，要求时间复杂度为O(1)

class Solution:    def deleteNode(self, node):        next_node=node.next        next_nextnode=next_node.next        node.val=next_node.val        node.next=next_nextnode

反转链表

class Solution:    def reverseList(self, head: ListNode) -> ListNode:        pre=None        # 不断取出和向后移动头节点,并将头节点连接到新头节点后面        while head:            next_node=head.next            head.next=pre            pre=head            head=next_node        return pre

二叉树的层次遍历

class Node(object):    def __init__(self, data, left=None, right=None):        self.data = data        self.left = left        self.right = right tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4))) def lookup(root):    stack = [root]    while stack:        current = stack.pop(0)        print current.data        if current.left:            stack.append(current.left)        if current.right:            stack.append(current.right)def deep(root):    if not root:        return    print root.data    deep(root.left)    deep(root.right) if __name__ == '__main__':    lookup(tree)

判断一棵二叉树是否为另一棵二叉树的子树

class Solution(object):    def isSubtree(self, s, t):  #用于判断的主函数，递归得遍历s的每一个结点，并将其作为新的根节点，再与t进行比较        if not s:            return False                    return self.isEqual(s,t) or self.isSubtree(s.left,t) or self.isSubtree(s.right,t)        #使用or相连，即其中只要有一个s的子树与t相同，则返回True                    def isEqual(self,S,T):  #以S为根节点，判断S和T是否相等        if not S and not T:            return True        if S and T:            if S.val!=T.val:                return False            return self.isEqual(S.left,T.left) and self.isEqual(S.right,T.right)        else:            return False

二叉搜索树中第 K 小的元素

class Solution:    def kthSmallest(self, root: TreeNode, k: int) -> int:        stack=[]        res=[]        while root or stack:            if root:                stack.append(root)                root=root.left            else:                node=stack.pop()                res.append(node.val)                if len(res)==k:                    break                root=node.right        return res.pop()