数据结构与算法
算法概述
-
算法-前序
x1【1】Everybody!全场动作必须跟我整齐划一,来,我们一起来做一道题
2若n1+n2+n3=1000,且n1^2+n2^2=n3^2(n1,n2,n3为自然数),求出所有n1、n2、n3可能的组合
3
4【2】解题思路
5n1 = 0
6n2 = 0
7n3 = 0
8判断n1+n2+n3是否等于1000,之后变n3=1,n3=2,n3=3,... 然后再变n2
9
10【3】代码实现
11import time
12
13start_time = time.time()
14for n1 in range(0,1001):
15for n2 in range(0,1001):
16for n3 in range(0,1001):
17if n1 + n2 + n3 == 1000 and n1**2 + n2**2 == n3**2:
18print('[%d,%d,%d]' % (n1,n2,n3))
19end_time = time.time()
20print('执行时间:%.2f' % (end_time-start_time))
2122【4】算法概念
234.1) 解决问题的方法,是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令
244.2) 算法代表着用系统的方法描述解决问题的策略机制
时间复杂度概述
-
时间复杂度 - 前序
xxxxxxxxxx
161【1】各位,一万年太久,只争朝夕,来提升一下上题的效率吧!!!
2for n1 in range(0,1001):
3for n2 in range(0,1001):
4n3 = 1000 - n1 - n2
5if n1**2 + n2**2 == n3**2:
6print('[%d,%d,%d]'%(n1,n2,n3))
7
8【2】总结与思考 : 解决同一个问题有多种算法,但是效率有区别,那么如何衡量呢?
92.1) 执行时间反应算法效率 - 绝对靠谱吗?
10不是绝对靠谱: 因机器配置有高有低,不能冒然绝对去做衡量
11122.2) 那如何衡量更靠谱???
13运算数量 - 执行步骤的数量
1415【4】时间复杂度概念
164.1) 同一个算法,由于机器配置差异,每台机器执行的总时间不同,但是执行基本运算的数量大体相同,所以把算法执行步骤的数量称为时间复杂度
-
时间复杂度 - 大O表示法前序
xxxxxxxxxx
241################################################################
2【1】计算此算法的时间复杂度
3for n1 in range(0,1001):
4for n2 in range(0,1001):
5for n3 in range(0,1001):
6if n1 + n2 + n3 == 1000 and n1**2 + n2**2 == n3**2:
7print('[%d,%d,%d]' % (n1,n2,n3))
8################################################################
9【2】计算步骤
10T = 1000 * 1000 * 1000 * 2
11T = n * n * n * 2
12T(n) = n ** 3 * 2 即时间复杂度为: T(n)=n**3 * 2
13
14【3】时间复杂度T(n)的 大O表示法
153.1) 函数1: T(n)=k * n**3 + c
163.2) 函数2: g(n)=n**3
173.3) 特点: 在趋向无穷的极限意义下,函数T(n)的增长速度受到函数g(n)的约束,也为函数T(n)与函数g(n)的特征相似,则称 g(n) 是 T(n) 的渐近函数,大O表示法则使用渐近函数来表示
18即: O(g(n))
19即: O(n^3)
20即: 上述时间复杂度为 O(n^3)
21
22【4】时间复杂度总结
234.1) 假设存在函数g,使得算法A处理规模为n的问题所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n)
244.2) 对算法进行特别具体细致分析虽然好,但实践中实际价值有限。对我们来说算法的时间性质和空间性质最重要的是数量级和趋势,这些是分析算法效率的主要部分。所以忽略系数,忽略常数,比如5*n^2 和 100*n^2属于一个量级,时间复杂度为O(n^2)
-
时间复杂度分类
xxxxxxxxxx
51【1】最优时间复杂度 - 最少需要多少个步骤
2【2】最坏时间复杂度 - 最多需要多少个步骤
3【3】平均时间复杂度 - 平均需要多少个步骤
4
5我们平时所说的时间复杂度,指的是最坏时间复杂度
时间复杂度 - 计算规则
-
计算原则
xxxxxxxxxx
211【1】基本操作,只有常系数,认为其时间复杂度为O(1)
2顺序 - 基本步骤之间的累加
3print('abc') -> O(1)
4print('abc') -> O(1)
5
6【2】循环: 时间复杂度按乘法进行计算
78【3】分支: 时间复杂度取最大值(哪个分支执行次数多算哪个)
9
10【4】练习:请计算如下代码的时间复杂度
11for n1 in range(0,1001):
12for n2 in range(0,1001):
13n3 = 1000 - n1 - n2
14if n1**2 + n2**2 == n3**2:
15print('[%d,%d,%d]'%(n1,n2,n3))
1617T(n) = n * n * (1+1+max(1,0))
18T(n) = n**2 * 3
19T(n) = n**2
20T(n) = O(n**2)
21用大O表示法表示为 Tn = O(n^2)
-
常见时间复杂度
执行次数 时间复杂度 阶 20(20个基本步骤) O(1) 常数阶 8n+6 O(n) 线性阶 2n^2 + 4n + 2 O(n^2) 平方阶 8logn + 16 O(logn) 对数阶 4n + 3nlogn + 22 O(nlog(n)) nlog阶 2n^3 + 2n^2 + 4 O(n^3) 立方阶 2 ^ n O(2^n) 指数阶 -
O(1)
xxxxxxxxxx
91【1】O(1)
2print('全场动作必须跟我整齐划一')
3
4【2】O(1)
5print('左边跟我一起画个龙')
6print('在你右边画一道彩虹')
7print('走起')
8print('左边跟我一起画彩虹')
9print('在你右边再画一条龙')
-
O(n)
xxxxxxxxxx
21for i in range(n):
2print('在胸口比划一个郭富城')
-
O(n^2)
xxxxxxxxxx
101【1】O(n^2)
2for i in range(n):
3for j in range(n):
4print('左边右边摇摇头')
56【2】O(n^2)
7for i in range(n):
8print('两根手指就像两个窜天猴')
9for j in range(n):
10print('指向闪耀的灯球')
-
O(n^3)
xxxxxxxxxx
41for i in range(n):
2for j in range(n):
3for k in range(n):
4print('走你')
-
O(logn)
xxxxxxxxxx
81n = 64
2while n > 1:
3print(n)
4n = n // 2
5
6【解释】
72的6次方 等于 64,log264 = 6,所以循环减半的时间复杂度为O(log2n),即O(logn)
8如果是循环减半的过程,时间复杂度为O(logn)或O(log2n)
-
O(nlogn)
xxxxxxxxxx
51n = 64
2while n > 1:
3for i in range(n):
4print('哪里有彩虹告诉我')
5n = n // 2
-
常见时间复杂度排序
xxxxxxxxxx
11O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
-
练习: 写出如下的时间复杂度
xxxxxxxxxx
41O(5) --> O(1)
2O(2n+1) --> O(n)
3O(n**2+n+1) --> O(n**2)
4O(3n**3+1) --> O(n**3)
-
终极总结两句话
xxxxxxxxxx
21【1】时间复杂度是多少: T(n) = O(???)
2【2】去掉系数、去掉常数、去掉低次幂,最终得到时间复杂度
数据结构概述
-
数据结构描述
xxxxxxxxxx
91【1】概述
21.1) 在工作中,我们为了解决问题,需要将数据保存下来,然后根据数据存储方式设计算法进行处理,根据数据的存储方式我们使用不同的算法处理,而我们现在需要考虑算法解决问题的效率问题,所以需要考虑数据究竟如何保存,这就是数据结构
34【2】概念
52.1) 数据是一个抽象的概念,将其进行分类后得到程序设计语言中的基本类型,如:list、tuple等。数据元素之间不是独立的,存在特定的关系,这些关系便是结构。数据结构指数据对象中数据元素之间的关系
62.2) Python提供了很多现成的数据结构类型,如列表、元组、字典等,无须我们自己去定义,而Python没有定义的,就需要我们自己去定义实现这些数据的组织方式,称为Python扩展数据结构,如:栈、队列等
7
8【3】为什么学习数据结构
9在真正的项目开发中,大部分时间都是从数据库取数据 -> 数据操作和结构化 -> 返回给前端,在数据操作过程中需要合理地抽象,组织、处理数据,如果选用了错误的数据结构,就会造成代码运行低效
-
数据结构分类
xxxxxxxxxx
91【1】线性结构 : n个数据元素的有序集合
21.2) 顺序表 : 将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中
31.3) 链表 : 将数据结构中各元素分布到存储器的不同点,用记录下一个结点位置的方式建立它们之间的联系
41.4) 栈 : 后进先出
51.5) 队列 : 先进先出
67【2】非线性结构
82.1) 树形结构
92.2) 图状结构
-
数据结构+算法总结
xxxxxxxxxx
41【1】数据结构只是静态描述了数据元素之间的关系
2【2】高效的程序需要在数据结构的基础上设计和选择算法
3【3】程序 = 数据结构 + 算法
4【4】算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体
抽象数据类型
-
概念
xxxxxxxxxx
121【1】定义
2抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作,及把数据类型和数据类型上的运算捆在一起进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上的运算的实现与这些数据类型和运算在程序中的引用隔开,使他们相互独立
3
4【2】描述
5把原有的基本数据和这个数据所支持的操作放到一起,形成一个整体
6
7【3】最常用的数据运算
83.1) 插入
93.2) 删除
103.3) 修改
113.4) 查找
123.5) 排序
线性表 - 顺序表
-
顺序表的基本形式
xxxxxxxxxx
41【1】特点 : 内存连续
2【2】分类
32.1) 基本形式: 数据元素本身连续存储,每个元素所占存储单元大小固定相同
42.2) 元素外置: 数据元素不连续存储,地址单元连续存储
线性表 - 链表
-
定义
xxxxxxxxxx
51【1】特点:
21.1) 内存不连续的,而是一个个串起来的,需要每个链表的节点保存一个指向下一个节点的指针
34【2】和顺序表的对比
52.1) 顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,使用起来不灵活,而链表结构可以充分利用计算机的内存空间,实现灵活的内存动态管理
-
示例 - 强化理解
xxxxxxxxxx
11将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块,称为结点,每个结点(尾节点除外)中都持有一个指向下一个节点的引用,这样所得到的存储结构为链表结构
-
单链表 - 代码实现
xxxxxxxxxx
1101"""
2创建单链表的数据结构:
31、节点类 - 数据区、链接区
42、单链表类(数学模型): 增加、删除... ...
5"""
6
7class Node:
8"""节点类"""
9def __init__(self, value):
10self.value = value
11self.next = None
12
13class SingleLinkList:
14"""单链表类"""
15def __init__(self, node=None):
16"""创建链表时: s=SingleLinkList()表示空链表,s=SingleLinkList(Node(100)) 表示有1个节点的单链表"""
17self.head = node
18
19def is_empty(self):
20"""判断链表是否为空"""
21return self.head == None
22
23def lengh(self):
24"""获取链表长度"""
25# 游标:从头节点开始,一直往后移动,移动一次,+1
26current = self.head
27count = 0
28while current is not None:
29count += 1
30current = current.next
31
32return count
33
34def travel(self):
35"""遍历整个链表"""
36current = self.head
37while current is not None:
38print(current.value,end=" ")
39current = current.next
40# 因为上面是end=" ",所以此处打印一个换行
41print()
42
43def add(self, item):
44"""链表头部添加1个节点"""
45node = Node(item)
46# 1、把新添加的节点指针指向原来头节点
47node.next = self.head
48# 2、添加的节点设置为新的头
49self.head = node
50
51def append(self, item):
52"""链表尾部添加1个节点,考虑空链表特殊情况"""
53node = Node(item)
54if self.is_empty():
55self.head = node
56else:
57current = self.head
58while current.next is not None:
59current = current.next
60# 循环结束后,current指向尾节点
61current.next = node
62node.next = None
63
64def search(self, item):
65"""查看在链表中是否存在"""
66current = self.head
67while current != None:
68if current.value == item:
69return True
70else:
71current = current.next
72
73return False
74
75def insert(self, pos, item):
76"""在指定索引添加一个节点,索引值从0开始"""
77if pos < 0:
78self.add(item)
79elif pos > self.lengh() - 1:
80self.append(item)
81else:
82pre = self.head
83count = 0
84while count < (pos - 1):
85count += 1
86pre = pre.next
87
88# 循环结束后,pos指向(pos-1)位置
89node = Node(item)
90node.next = pre.next
91pre.next = node
92
93if __name__ == '__main__':
94s = SingleLinkList()
95# 终端1:True
96print(s.is_empty())
97# 链表:Node(100) -> Node(200) -> Node(300)
98s.add(200)
99s.add(100)
100s.append(300)
101# 终端2:3
102print(s.lengh())
103# 终端3:100 200 300
104s.travel()
105# 100 666 200 300
106s.insert(1, 666)
107# 终端4: 100 666 200 300
108s.travel()
109# 终端5: True
110print(s.search(666))
链表练习一
-
题目
xxxxxxxxxx
71【1】题目描述
2输入一个链表,按链表值从尾到头的顺序返回一个 ArrayList
34【2】试题解析
5将链表的每个值取出来然后存放到一个列表 ArrayList 中
6解题思路1: 将链表中从头节点开始依次取出节点元素,append到array_list中,并进行最终反转
7解题思路2: 将链表中从头节点开始依次取出节点元素,insert到array_list中的第1个位置
-
代码实现
xxxxxxxxxx
261"""
2输入一个链表,按链表值从尾到头的顺序返回一个 ArrayList
3"""
4
5class Node:
6"""链表节点类"""
7def __init__(self,x):
8self.val = x
9self.next = None
10
11class Solution:
12# 返回从尾部到头部的序列,node为头节点
13def get_list_from_tail_to_head(self,node):
14array_list = []
15while node:
16array_list.insert(0,node.val)
17node = node.next
18
19return array_list
20
21if __name__ == '__main__':
22s = Solution()
23head = Node(100)
24head.next = Node(200)
25head.next.next = Node(300)
26print(s.get_list_from_tail_to_head(head))
链表练习二
-
题目
xxxxxxxxxx
51【1】题目描述
2输入一个链表,反转链表后,输出新链表的表头
34【2】试题解析
5可以将链表的每一个节点取出来,插入到新的链表表头,同时要保存原链表的下一个节点
-
代码实现
x
1"""
2输入一个链表,反转链表后,输出新链表的表头
3思路:
41、创建2个游标,代表要进行反转操作的节点 和 上一个节点
52、代码逻辑:
6当前节点指针指向上一个节点
7两个游标同时往后移动
8结束标准: 当要操作的节点为None时,结束! 此时pre代表的是新链表的头节点
9"""
10class Node:
11def __init__(self, value):
12self.value = value
13self.next = None
14
15class Solution:
16def reverse_link_list(self, head):
17# 1、空链表情况
18if head == None:
19return
20# 2、非空链表情况
21pre = None
22cur = head
23while cur:
24# 记录下一个要操作反转的节点
25next_node = cur.next
26# 反转节点cur,并移动两个游标
27cur.next = pre
28pre = cur
29cur = next_node
30
31return pre.value
32
33if __name__ == '__main__':
34s = Solution()
35# 1、空链表情况
36head = None
37print(s.reverse_link_list(head))
38# 2、只有1个节点情况
39head = Node(100)
40print(s.reverse_link_list(head))
41# 3、有多个节点情况
42head = Node(100)
43head.next = Node(200)
44head.next.next = Node(300)
45print(s.reverse_link_list(head))
线性表 - 栈(LIFO)
-
定义
xxxxxxxxxx
11栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许进行操作的一端称为"栈顶",另一固定端称为"栈底",当栈中没有元素时称为"空栈"
-
特点
xxxxxxxxxx
21【1】栈只能在一端进行数据操作
2【2】栈模型具有后进先出的规律(LIFO)
-
栈的代码实现
xxxxxxxxxx
471# 栈的操作有入栈(压栈),出栈(弹栈),判断栈是否为空等操作
2"""
3sstack.py 栈模型的顺序存储
4重点代码
5
6思路:
71. 利用列表完成顺序存储,但是列表功能多,不符合栈模型特点
82. 使用类将列表封装,提供符合栈特点的接口方法
9"""
10
11# 顺序栈模型
12class Stack(object):
13def __init__(self):
14# 开辟一个顺序存储的模型空间
15# 列表的尾部表示栈顶
16self.elems = []
17
18def is_empty(self):
19"""判断栈是否为空"""
20return self.elems == []
21
22def push(self,val):
23"""入栈"""
24self.elems.append(val)
25
26def pop(self):
27"""出栈"""
28if self.is_empty():
29raise StackError("pop from empty stack")
30# 弹出一个值并返回
31return self.elems.pop()
32
33def top(self):
34"""查看栈顶元素"""
35if self.is_empty():
36raise StackError("Stack is empty")
37return self.elems[0]
38
39
40if __name__ == '__main__':
41st = Stack()
42st.push(1)
43st.push(3)
44st.push(5)
45print(st.top())
46while not st.is_empty():
47print(st.pop())
线性表 - 队列(FIFO)
-
定义
xxxxxxxxxx
11队列是限制在两端进行插入操作和删除操作的线性表,允许进行存入操作的一端称为"队尾",允许进行删除操作的一端称为"队头"
-
特点
xxxxxxxxxx
211) 队列只能在队头和队尾进行数据操作
22) 队列模型具有先进先出规律(FIFO)
-
队列的代码实现
x
1# 队列的操作有入队,出队,判断队列的空满等操作
2"""
3思路分析:
41. 基于列表完成数据的存储
52. 通过封装功能完成队列的基本行为
63. 无论那边做对头/队尾 都会在操作中有内存移动
7"""
8
9# 队列操作
10class SQueue:
11def __init__(self):
12self.elems = []
13
14# 判断队列是否为空
15def is_empty(self):
16return self.elems == []
17
18# 入队
19def enqueue(self,val):
20self.elems.append(val)
21
22# 出队
23def dequeue(self):
24if not self._elems:
25raise Exception("Queue is empty")
26return self.elems.pop(0) # 弹出第一个数据
27
28
29if __name__ == '__main__':
30sq = SQueue()
31sq.enqueue(10)
32sq.enqueue(20)
33sq.enqueue(30)
34while not sq.is_empty():
35print(sq.dequeue())