赞
踩
算法:一个计算过程,解决问题的方法
程序=数据结构+算法
数据:列表、字典
数据结构:数据的存储
算法:数据的动态过程
时间复杂度的目的是通过一种类似于公式的方式不通过运行来发现某种算法其运行快慢和优劣。
O:估计、大约
(1):一个运行单位
print("hello,world")
for i in range(n):
print("hello,world")
for i in range(n):
for j in range(n):
print("hello,world")
时间复杂度为log_2n,见下
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)
每次问题规模减半的时候,时间复杂度会出现log
while n>1:
print(n)
n=n//2
小结:
时间复杂度是用来估计算法运行时间的一个式子(单位)。
一般来说,时间复杂度高的算法比复杂度低的算法慢。
常见的时间复杂度(按效率排序)
O
(
1
)
<
O
(
l
o
g
2
n
)
<
O
(
n
)
<
O
(
n
l
o
g
2
n
)
<
O
(
n
2
)
<
O
(
n
2
l
o
g
2
n
)
<
O
(
n
3
)
O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^2log_2n)<O(n^3)
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n2log2n)<O(n3)
复杂问题的时间复杂度
如何简单快速地判断算法复杂度:
用来评估算法内存占用大小的式子
空间复杂度的表示方式与时间复杂度完全一致
算法使用了几个变量:O(1)
算法使用了长度为n的一维列表:O(n)
算法使用了m行n列的二维列表:O(mn)
空间换时间
递归的两个特点:
上述函数为死递归没有结束条件
def func1(x):
print(x)
func(x-1)
看似加了一个递归,但是条件是个伪条件,仍是个死递归
def func2(x):
if x>0:
print(x)
func2(x+1)
合法的递归,会打印x
def func3(x):
if x>0:
print(x)
func3(x-1)
合法的递归,会打印x-1
def func4(x):
if x>0:
func4(x-1)
print(x)
汉诺塔问题
n个盘子时:
- 把n-1个盘子从A经过C移动到B
- 把第n个圆盘从A移动到C
- 把n-1个小圆盘从B经过A移动到C
def hanoi(n,a,b,c):
if n>0:
hanoi(n-1,a,c,b)
print("moving from %s to %s"%(a,c))
hanoi(n-1,b,a,c)
查找:在一些数据元素中,通过一定的方法找出与给定关键词相同的数据元素的过程
列表查找:从列表中查找指定元素
输入:列表、待查找元素
输出:元素下标(未找到元素时一般返回None或-1)
内置列表查找函数:index()
顺序查找:也叫线性查找,从列表第一个元素开始,顺序进行搜索,直到找到元素或搜索到列表最后 一个元素为止。
def linear_search(li,val):
for ind,v in enumerate(li):
if v==val:
return ind
else:
return None
时间复杂度O(n)
二分查找:又称折半查找,从有序列表的初始候选区li[0:n]开始,通过对待查找的值与候选区中间值的比较,可以使候选区减少一半。
def binary_search(li,val):
left=0
right=len(li)-1
while left<=right: #候选区有值
mid=(left+right)//2
if li[mid]==val:
return mid
elif li[mid]>val: #代表接下来的候选区在mid的左边
right=mid-1
else: #li[mid]<val 待查找的值在mid右侧
left=mid+1
else:
return None
时间复杂度:O(logn)
排序:将一组”无序“的记录序列调整为”有序“的记录序列
列表排序:将无序列表变成有序列表
输入:列表
输出:有序列表
升序与降序
内置排序函数:sort()
含义:
代码关键点:趟、无序区范围(第i趟指针会运行n-i-1趟)
def bubble_sort(li):
for i in range(len(li)-1): #i表示第i趟
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
时间复杂度:O(n^2)
def select_sort_simple(li):
li_new=[]
for i in range(len(li)):
min_val=min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
时间复杂度:O(n^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
li[i],li[min_loc]=li[min_loc],li[i]
时间复杂度:O(n^2)
def insert_sort(li):
for i in range(1,len(li)): #i表示摸到的牌的下标
tmp=li[i]
j=i-1 #j表示的就是手里的牌的下标
while li[j]>tmp and j>=0:
li[j+1]=li[j]
j-=1
li[j+1]=tmp
思路:
快速排序框架
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)
partition函数
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >=tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
时间复杂度:O(nlogn)
最坏的情况:
树是一种数据结构 比如:目录结构
数是一种可以递归定义地数据结构
树是由n个节点组成地集合:
如果n=0,那这是一棵空树;
如果n>0,那存在1个节点作为树地根节点,其他节点可以分为m个集合,每个集合本身又是一棵树
一些概念:
根节点:下面还有分叉
叶子节点:下面没有分叉,到末尾了
有几层就有几个节点
节点的度:下面分几个叉
树的度:最大的节点的度
上面分叉的就是父节点
被分下来的就是孩子节点
一个树一部分被截取下来叫做子树
二叉树:每个节点最多分两个叉的树
每一层的结点都达到最大值,称满二叉树
叶子节点只能出现在最下层和次下层,并且最下层的节点都集中在该层最左边若干位置的二叉树
一定要最下面一层从左往右依次排列
二叉树的存储方式
父节点和左孩子节点的编号下标i–>2i+1
父节点和右孩子节点的编号下标i–>2i+2
堆:一种特殊的完全二叉树
堆的向下调整:
父节点比下级子节点小,就需要从下面开始向上调整
当根节点的左右子树都是堆时,但是根自身不满足,可以通过一次向下调整来将其变换成一个堆
堆排序的过程:
函数的调整过程
def sift(li ,low,high): """ li:列表 low:堆的堆顶位置 high:堆的最后一个元素的位置 """ i=low #i最开始指向根节点 j=2*i+1 #j开始是左孩子 tmp=li[low] #把堆顶存起来 while j<=high: #只要j和j+1位置有节数 if li[j+1]>li[j] and j+1<=high: j=j+1 #j指向右孩子 if li[j]>tmp: li[i]=li[j] i=j #往下看一层 j=2*i+1 else: #tmp更大,把tmp放在i的位置上 li[i]=tmp #把tmp放在某一级领导位置上 break else: li[i]=tmp #把tmp放在叶子节点上
堆排序
def heap_sort(li):
n=len(li)
for i in range((n-2)//2,-1,-1):
sift(li,i,n-1)
#建堆完成了
for i in range(n-1,-1,-1):
#i指向当前堆的最后一个函数
li[0],li[i]=li[i],li[0]
sift(li,0,i-1) #i-1是新的high
时间复杂度:O(nlogn)
堆的内置模块:heapq
import heapq q-->quence 优先队列
import random
li=list(range(100))
random.shuffle(li)
heapq.heapify(li) #建堆
n=len(li)
for i in range(n):
heapq.heappop(li) #每次弹出一个最小的元素
堆排序——topk问题
现有n个数,设计算法得到前k大的数。(k<n)
解决思路:
排序后切片 O(nlogn)+k(切片的过程)
排序lowb三人组 O(kn)
堆排序思路 O(nlogk)
1. 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数。
1. 依次向后遍历原列表,对于列表中的元素,如果小于堆顶,则忽略该元素;如果大于堆顶,则将堆顶更换为该元素,并且对堆进行一次调整。
1. 遍历列表所有元素后,倒序弹出堆顶
def sift(li ,low,high): """ li:列表 low:堆的堆顶位置 high:堆的最后一个元素的位置 """ i=low #i最开始指向根节点 j=2*i+1 #j开始是左孩子 tmp=li[low] #把堆顶存起来 while j<=high: #只要j和j+1位置有节数 if li[j+1]<li[j] and j+1<=high: j=j+1 #j指向右孩子 if li[j]<tmp: li[i]=li[j] i=j #往下看一层 j=2*i+1 else: #tmp更大,把tmp放在i的位置上 li[i]=tmp #把tmp放在某一级领导位置上 break else: li[i]=tmp #把tmp放在叶子节点上 def topk(li,k): heap=[0:k] for i in range((k-2)//2,-1,-1): sift(heap,i,k-1) #1. 建堆 for i in range(k,len(li)-1): heap[0]=li[i] sift(heap,0,k-1) #2. 遍历 for i in range(k-1,-1,-1): heap[0],heap[i]=heap[i],heap[0] sift(heap,0,i-1) #3. 出数 return heap
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执行完,肯定有一部分没数了 while i<=mid: ltmp.append(li[i]) i+=1 while j<=high: ltmp.append(li[j]) j+=1 li[low:high+1]=ltmp
归并排序——使用归并
分解:将列表越分越小,直至分成一个元素
终止条件:一个元素是有序的
合并:将两个有序列表合并,列表越分越大
def merge_sort(li,low,high):
if low<high: #至少有两个元素,递归
mid=(low+high)//2
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)
时间复杂度:O(nlogn)
空间复杂度:O(n)
三种排序算法的时间复杂度都是O(nlogn)
一般情况下,就运行时间而言:
快速排序<归并排序<堆排序
三种排序算法的缺点:
快速排序:极端情况下排序效率低
归并排序:需要额外的内存开销
堆排序 :在快的排序算法中相对较缓
希尔排序是一种分组插入排序算法
首先取一个整数d1=n//2,将元素分为d1个组,每组相邻两个元素之间的距离为d1.在各组内进行直接插入排序
取第二个整数d2=d1//2,重复上述分组排序过程,直到di=1,即所有元素在同一组内进行直接插入排序
希尔排序每趟并不使某些元素有序,而是使整体数据越来越接近有序;最后一趟排序使得所有数据有序
def insert_sort_gap(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 shell_sort(li):
d=len(li)//2
while d>=1:
insert_sort_gap(li,d)
d//2
对列表进行排序,已知列表中的数的范围都在0到100之间。设计时间复杂度为O(n)的算法
def count_sort(li,max_count):
count=[0 for _ in range(max_count+1)]
for val in li:
count[val]+=1
li.clear()
for ind,val in enumerate(count):
for i in range(val):
li.append(ind)
桶排序:首先将元素分在不同的桶里,再对每个桶的元素排序
def bucket_sort(li,n=100,max_num=10000):
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],buckets[i][j-1]=buckets[i][j-1],buckets[i][j]
else:
break
sorted_li=[]
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
线性结构:数据结构中的元素存在一对一的相互关系
树结构 :数据结构中的元素存在一对多的相互关系
图结构 :数据结构中的元素存在多对多的相互关系
栈式一个数据集合,可以理解为只能在一端进行插入或删除操作的列表
栈的特点:后进先出
栈的概念:栈顶、栈底LIFO(last-in,first-out)
栈的基本操作:
进栈: push
出栈: pop
取栈顶:gettop
栈的实现:
li.append() #进栈
li.pop() #出栈
li[-1] #取栈顶
def Stack:
def __init__(self):
self.stack=[]
def push(self,element):
self.stack.append(element)
def pop(self):
return self.stack.pop()
def get_top(self):
if len(self.stack)>0:
return self.stack[-1]
else:
return None
队列是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除
进行插入的一端称为队尾,插入的动作称为进队或入队
进行删除的一端称为队头,删除的动作称为出队
队列的性质:先进先出
环形队列:当队尾指针front==maxsize-1时,再前进一个位置就自动到0
队首指针前进1:front=(front+1)%maxsize
队尾指针前进1:rear=-(rear+1)%maxsize
队空条件 :rear==front
队满条件 :(rear+1)%maxsize==front
class Queue: def __init__(self,size=100): self.queue=[0 for _ in range(size)] self.size=size self.rear=0 #队尾 self.front=0 #队首 def push(self,element): if not self.is_filled(): rear=(self.rear+1)%self.size self.queue[self.rear]=element else: raise IndexError("Queue is filled") def pop(self): if not self.is_empty(): self.front=(self.front+1)%self.size return self.queue[self.front] else: raise IndexError("Queue is mpty") def is_empty(self): return self.rear==self.front def is_filled(self): return (self.rear+1)%self.size==self.front
双向队列的两端都支持进队和出队操作
双向队列的基本操作:
队首进队
队首出队
队尾进队
队尾出队
from collections import deque
#deque 双向队列
q=deque()
q.append(1)#队首进队
q.popleft()#队首出队
q.appendleft(1)#队首进队
q.pop()#队尾出队
回溯法
思路:从一个节点开始,任意找下一个能走的点,当找不到能走的点时,退回上一个点寻找是否有其他方向的带点
使用栈存储当前路径
maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] dirs = [ lambda x,y: (x - 1, y), # 上 lambda x,y: (x, y + 1), # 右 lambda x,y: (x + 1, y), # 下 lambda x,y: (x, y - 1) # 左 ] def maze_path(x1, y1, x2, y2): stack = [] stack.append((x1, y1)) while(len(stack) > 0): # 栈空表示没有路 current_node = stack[-1] # 当前节点 # 判断当前是否走到了终点 if current_node[0] == x2 and current_node[1] == y2: # 把路径打印出来 for p in stack: print(p) return True # x, y四个方向: x, y-1; x+1, y; x, y+1; x-1, y for dir in dirs: next_node = dir(current_node[0], current_node[1]) # 如果下一个节点能走 if maze[next_node[0]][next_node[1]] == 0: stack.append(next_node) maze[next_node[0]][next_node[1]] = 2 # 表示已经走过 break else: # 如果4个位置都不能走了,该点就出栈 maze[current_node[0]][current_node[1]] = 2 stack.pop() else: print("无路可走,走投无路") return False maze_path(1, 1, 8, 8)
思路:从一个节点开始,寻找所有接下来能继续走的点,继续不断寻找,直到找到出口
使用队列存储当前正在考虑的节点
from collections import deque maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] # x,y四个方向分别为:x+1,y; x-1,y; x,y+1; x,y-1 dirs = { lambda x, y: (x + 1, y), lambda x, y: (x - 1, y), lambda x, y: (x, y + 1), lambda x, y: (x, y - 1) } # 输出path def print_r(path): curNode = path[-1] # 当前的最后一个节点就是终点,但是path有很多挑路径,挑能走到终点那条路径 realpath = [] while curNode[2] != -1: realpath.append(curNode[:2]) # 把节点放到真实路径 curNode = path[curNode[2]] # 挑能走到终点那条路 realpath.append(curNode[0:2]) # -1跳出来了,-1为起点,把起点放进去 realpath.reverse() # 把列表倒过来 for node in realpath: print(node) def maze_path_queue(x1, y1, x2, y2): # x1,y1代表起点,x2,y2代表终点 queue = deque() queue.append((x1, y1, -1)) # 起始点和谁让它来的 path = [] while len(queue) > 0: curNode = queue.popleft() # 当前节点是队首节点,并将队首节点出队 path.append(curNode) # 把出队的节点放在另一个列表parh里 if curNode[0] == x2 and curNode[1] == y2: # 终点 print_r(path) return True for dir in dirs: nextNode = dir(curNode[0], curNode[1]) if maze[nextNode[0]][nextNode[1]] == 0: queue.append((nextNode[0], nextNode[1], len(path) - 1)) # curNode让nextNode来的,curNode就是path的最后一个节点 maze[nextNode[0]][nextNode[1]] = 2 # 标记已经走过 else: # 没有一个节点能走 print('没有路!') return False maze_path_queue(1, 1, 8, 8)
链表是由一系列节点组成的元素集合。每个节点包含两部分,数据域item和指向下一个节点的指针next。通过节点之间的相互连接,最终串联成一个链表。
class Node(object):
def __init__(self,item):
self.item=item
self.next=None
"""
手动创建链表
"""
a=Node(1)
b=Node(2)
c=Node(3)
a.next=b
b.next=c
从头部开始
def creat_linklist_head(li):
head=Node(li[0])#第一个节点
for element in li[1:]:#从第2个元素到最后
node=Node(element)#将元素从第2个到最后开始排
node.next=head#节点的下一个是头节点
head=node#头节点等于节点
return head
def creat_linklist_tail(li):
head=Node(li[0])
tail=head
for element in li[1:]:
node=Node(element)
tail.next=node
tail=node
return head
链表插入:先连接再锻炼
p.next=curNode.next
curNode.next=p
链表节点的删除
p=curNode.next
curNode.next=curNode.next.next
del p
哈希表一个通过哈希函数来计算数据存储位置的数据结构,通常支持如下操作:
insert(key,value):插入键值对(key,value)
get(key):如果存在建为key的键值对则返回其value,否则返回空值
delete(key):删除键为key的键值对
直接寻址技术的缺点:
当域U很大时,需要消耗大量内存,很不实际
如果域U很大而且实际出现的key很少,则大量空间被浪费
无法处理关键字不是数字的情况
直接寻址表:key为k的元素放到k位置上
改进直接寻址表:哈希(Hashing)
构建大小为m的寻指标T
key为k的元素放到h(k)位置上
h(k)是一个函数,其将域U映射到表T[0,1,…,m-1]
哈希表,是一种线性表的存储结构。哈希表由一个直接寻指标和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标。
class Node:
def __init__(self,name,type="dir"):
self.name=name
self.type=type
self.children=children
self.parent=None
n=Node("hello")
n2=Node("world")
n.children.append(n2)
n2.parent=n
二叉树的链式存储:将二叉树的节点定义为一个对象,节点之间通过类似链表的连接方式来连接
class BiTreeNode: def __init__(self,data): self.data=data self.lchild=None self.rchild=None a=BiTreeNode("A") b=BiTreeNode("B") c=BiTreeNode("C") d=BiTreeNode("D") e=BiTreeNode("E") f=BiTreeNode("F") g=BiTreeNode("G") e.lchild=a e.rchild=g a.rchild=c c.lchild=b c.rchild=d c.rchild=f root=e
def pre_order(root):
if root:
print(root.data)
pre_order(root.lchild)
pre_order(root.rchild)
def in_order(root):
if root:
in_order(root.lchild)
print(root.data)
in_order(root.rchild)
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data)
from collections import deque
def level_order(root):
queue=deque
queue.append(root)
while len(queue)>0:
node=queue.popleft()
print(node,data,end="")
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
二叉搜索树是一颗二叉树且满足性质:设x是二叉树的一个节点。如果y是x左子树的一个节点,那么y.key<=x.key;如果y是x右子树的一个节点,那么y.key>=x.key。
二叉搜索树的操作:查询、插入、删除
在对问题求解时,总是做出当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法并不保证会得到最优解,但是在某些问题上贪心算法的解就是最优解。要学会判断一个问题能否用贪心算法来计算。
t=[100,50,20,5]
def change(t,n):
m=[0 for _ in range(len(t))]
for i ,money in enumerate(t):
m[i]=n//money
m=n%money
return m,n
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。