算法的时间复杂度

评判程序优劣的方法

  • 消耗计算机资源和执行效率
  • 计算算法执行的耗时

  • 时间复杂度(推荐)

时间复杂度

  • 评判标准:量化算法执行的操作/执行步骤的数量
  • 最重要的项:时间复杂度表达式最有意义的项

  • 大O记法对时间复杂度进行表示:O(量化表达式中最有意义的项)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def sumofN(n):
theSum = 0
for i in range(1, n+1):
theSum = thSum + i
return theSum

print(sumofN(10))
# 1 + n + 1 =====> n + 2 =====> O(n)
a = 5
b = 6
c = 10
for i in range(n):
for j in range(n):
x = i * i
y = j * j
z = i * j
for k in range(n):
w = a * k + 45
v = b * b
d = 33

# 3 + 3n**2 + 2n + 1 ====> 3n**2 + 2n ====> 3n**2 ====> n**2 ====> O(n**2)

常见的时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

特性:先进先出

应用:每个 web 浏览器都有一个返回按钮。当你浏览网页时,这些网页被放置在一个栈中(实际是网页的网址)。你现在查看的网页在顶部,你第一个查看的网页在底部。如果按‘返回’按钮,将按相反的顺序浏览刚才的页面。

用python实现一个简单的栈

需要实现的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
- Stack() 创建一个空的新栈。 它不需要参数,并返回一个空栈。
- push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
- pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
- peek() 从栈返回顶部项,但不会删除它。不需要参数。 不修改栈。
- isEmpty() 测试栈是否为空。不需要参数,并返回布尔值。
- size() 返回栈中的 item 数量。不需要参数,并返回一个整数。
class Stark():
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return len(self.items) - 1
def isEmpty(self):
return self,items == []
def size(self):
return len(self.items)

队列

  • 特性:先进先出
  • 应用场景:

  • 我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时,他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。如果你是最后一个,你必须等待你前面的所有其他任务打印

实现一个简单的队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- Queue() 创建一个空的新队列。 它不需要参数,并返回一个空队列。
- enqueue(item) 将新项添加到队尾。 它需要 item 作为参数,并不返回任何内容。
- dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
- isEmpty() 查看队列是否为空。它不需要参数,并返回布尔值。
- size() 返回队列中的项数。它不需要参数,并返回一个整数。
class Queue():
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)

应用(烫手的山芋)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
- 案例:烫手的山芋
- 烫手山芋游戏介绍:6个孩子围城一个圈,排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋,需要在计时器计时1秒后将山芋传递给下一个孩子,依次类推。规则是,在计时器每计时7秒时,手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束,最后剩下的孩子获胜。请使用队列实现该游戏策略,排在第几个位置最终会获胜。
- 准则:队头孩子的手里永远要有山芋。
queue = Queue()
kids = ['A','B','C','D','E','F']
for kid in kids:
queue.enqueue(kid)
while queue.size() > 1:
for i in range(6):
kid = queue.dequeue()
queue.enqueue(kid)
queue.dequeue()

print('获胜者为:', queue.dequeue())

双端队列

同队列相比,有两个头部和尾部。可以在双端进行数据的插入和删除,提供了单数据结构中栈和队列的特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
- Deque() 创建一个空的新 deque。它不需要参数,并返回空的 deque。
- addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。
- addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
- removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
- removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
- isEmpty() 测试 deque 是否为空。它不需要参数,并返回布尔值。
- size() 返回 deque 中的项数。它不需要参数,并返回一个整数。
class Dequeue():
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)

案例:回文检查

  • 回文是一个字符串,读取首尾相同的字符,例如,radar toot madam
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isHuiWen(s):
ex = True

q = Dequeue()

for ch in s:
q.addFront(ch)

for i in range(len(s)//2):
font = q.removeFront()
rear = q.removeRear()
if font != rear:
ex = False
break
return ex
print(isHuiWen('addan'))

链表和顺序表

顺序表

  • 集合中存储的元素是有顺序的,顺序表的结构可以分为两种形式:单数据类型和多数据类型。
  • python中的列表和元组就属于多数据类型的顺序表

  • 顺序表的弊端:顺序表的结构需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁。

链表

  • 相对于顺序表,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。
  • 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是每一个结点(数据存储单元)里存放下一个结点的信息(即地址)

构造链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
is_empty():链表是否为空

length():链表长度

travel():遍历整个链表

add(item):链表头部添加元素

append(item):链表尾部添加元素

insert(pos, item):指定位置添加元素

remove(item):删除节点

search(item):查找节点是否存在
  • 节点
1
2
3
4
class Node():
def __init__(self,item):
self.item = item
self.next = None
  • 链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Link():
# 构建一个空链表
def __init__(self):
self._head = None # 永远指向链表中的头节点
# 向链表的头部插入节点
def add(self, item):
node = Node(item)
node.next = self._head
self._head = node
def travel(self):
cur = self._head
# 链表为空则输出“链表为空”
if self._head = None:
print("链表为空")
while cur:
print(cur.item)
cur = cur.next
def isEmpty(self):
return self._head == None
def length(self):
cur = self._head
count = 0
while cur:
count += 1
cur = cur.next
return count
def search(self, item):
cur = self._head
find = False
while cur:
if cur.item == item:
find = True
break
cur = cur.next
return find

def append(self, item):
node = Node(item)
if self._head == None:
self._head = node
return

cur = self._head
pre = None
while cur:
pre = cur
cur = cur.next
pre.next = node
def insert(self, pos, item):
node = Node(item)

if pos < 0 or pos > self.length():
print("重新给pos赋值")

cur = self._head
pre = None

for i in range(pos):
pre = cur
cur = cur.next
pre.next = node
node.next = cur
def remove(self, item):
cur = self._head
pre = None

if self._head == None:
print("链表为空,没有可删除的节点")
return

# 删除的是第一个节点的情况
if self._head.item == item:
self._head = self._head.next
return

# 删除的不是第一个节点的情况
while cur:
pre = cur
cur = cur.next
if cur.item == item:
pre.next = cur.next
return

顺序查找

  • 当数据存储在诸如列表的集合中时,我们说这些数据具有线性或顺序关系。 每个数据元素都存储在相对于其他数据元素的位置。 由于这些索引值是有序的,我们可以按顺序访问它们。 这个过程产实现的搜索即为顺序查找。
  • 顺序查找原理剖析:

从列表中的第一个元素开始,我们按照基本的顺序排序,简单地从一个元素移动到另一个元素,直到找到我们正在寻找的元素或遍历完整个列表。如果我们遍历完整个列表,则说明正在搜索的元素不存在。

  • 代码实现:该函数需要一个列表和我们正在寻找的元素作为参数,并返回一个是否存在的布尔值。found 布尔变量初始化为 False,如果我们发现列表中的元素,则赋值为 True。
  • 有序列表:之前我们列表中的元素是随机放置的,因此在元素之间没有相对顺序。如果元素以某种方式排序,顺序查找会发生什么?我们能够在搜索技术中取得更好的效率吗?

  • 二分查找:一定是只可以被应用在有序列表中

有序列表对于我们的实现搜索是很有用的。在顺序查找中,当我们与第一个元素进行比较时,如果第一个元素不是我们要查找的,则最多还有 n-1 个元素需要进行比较。 二分查找则是从中间元素开始,而不是按顺序查找列表。 如果该元素是我们正在寻找的元素,我们就完成了查找。 如果它不是,我们可以使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素,就可以消除中间元素以及比中间元素小的一半元素。如果该元素在列表中,肯定在大的那半部分。然后我们可以用大的半部分重复该过程,继续从中间元素开始,将其与我们正在寻找的内容进行比较。

二分查找实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def sort(alist, item): # item就是我们要找的元素
low = 0 # 进行二分查找操作的列表中的第一个元素的下标
high = len(alist)
find = False

while low <= high:
mid = (low+high) // 2 # 中间元素的下标
if item > alist[mid]: # 我们要找的数比中间的数大,则意味着我们要找的数在中间元素的右侧
low = mid + 1
elif item < alist[mid]: # 我们要找的数比中间的数小,则我们要找的数在中间数的左侧
high = mid - 1
else:
find = True
break
return find
  • test
1
2
3
4
alist = [1,2,3,4,5,6,7]
print(sort(alist, 51))

output: False

二叉树

  • 根节点
  • 左叶子节点

  • 右叶子节点

  • 子树

  • 高度

二叉树的遍历

  • 广度遍历:逐层遍历
  • 深度遍历

  • 前序:根左右

  • 中序:左根右

  • 后序:左右根

构造普通二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Node():
def __init__(self, item):
self.item = item
self.left = None
self.right = None
class Tree():
# 构造出一颗空的二叉树
def __init__(self, item): # root指向第一个节点的地址,如果root指向了None,则意味着该二叉树为空
self.root = None
# 向二叉树中插入节点
def addNode(self, item):
node = Node(item)
if self.root == None:
# addNode如果第一次被调用则意味着:向空树中插入第一个节点,该节点一定是该树的根节点
self.root = node
return
# 如果上面的if不执行则树为非空,下面就执行向一个非空的树中插入节点的操作
cur = self.root
queue = [cur]
while queue:
n = queue.pop(0)
if n.left != None:
queue.append(n.left)
else:
n.left = node
break
if n.right != None:
queue.append(n.right)
else:
n.right = node
break
def travel(self):
# 如果为空
if self.root == None:
print("树为空!")
return

cur = self.root
queue = [cur]
while queue:
n = queue.pop(0)
print(n.item)
if n.left != None:
queue.append(n.left)
if n.right != None:
queue.append(n.right)
# 前序遍历
def forward(self, root):
if root == None:
return

print(root.item)
self.forward(root.left)
self.forward(root.right)

# 中序遍历
def middle(self, root):
if root == None:
return
self.middle(root.left)
print(root.item)
self.middle(root.right)

# 后序遍历
def back(self, root):
if root == None:
return
self.back(root.left)
self.back(root.right)
print(root.item)

构造排序二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Node():
def __init__(self, item):
self.item = item
self.left = None
self.right = None
class SortTree():
def __init__(self):
self.root = None
def insertNode(self, item):
node = Node(item)
# 向空树插入第一个节点
if self.root == None:
self.root = node
return
# 树为非空的情况
cur = self.root

while True:
if node.item > cur.item: # 往右插
if cur.right == None:
cur.right = node
break
else:
cur = cur.right
else: #往左插
if cur.left = None:
cur.left = node
break
else:
cur = cur.left

def forward(self, root):
if root == None:
return
print(root.item)
self.forward(root.left)
self.forward(root.right)

def middle(self, root):
if root == None:
return

self.middle(root.left)
print(root.item)
self.middle(root.right)

def back(self, root):
if root == None:
return

self.back(root.left)
self.back(root.right)
print(root.item)

五大排序算法

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
# 将列表元素中最大值找出放置在了列表中最后的位置
def sort(alist):
for i in range(0, len(alist)-1):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
print(alist)
def sort(alist):
for j in range(0, len(alist)-1):

for i in range(0, len(alist)-1-j): # 空值比较的次数
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
print(alist)

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 直接将列表中最大值找出,放在列表最后的位置
def sort(alist):
max = 0 # max中存储的是列表中元素值最大的数的下标,最开始先假设列表下标为0对应的元素是最大值
for i in range(0, len(alist)-1):
if alist[max] < alist[i+1]:
max = i+1
# 将最大值放置到列表末尾的位置
alist[max], alist[len(alist)-1] = alist[len(alist)-1], alist[max]
print(alist)
def sort(alist):
for j in range(len(alist)-1, 0, -1):
# max中存储的是列表中元素值最大的数的下标。最开始先假设列表下标为0对应的元素是最大值
max = 0
for i in range(0, j): # len(alist)-1 ==> j
if alist[max] < alist[i+1]:
max = i+1
# 将最大值放置到列表末尾的位置
alist[max],alist[j] = alist[j],alist[max]
print(alist)

插入排序(增量为1的希尔排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
alist = [3,8,5,7,6]

[3, 8,5,7,6]
[3,8, 5,7,6]
[3,5,8, 7,6]
[3,5,7,8, 6]
[3,5,6,7,8 ]
# step_1
i = 1 # 表示的是列表中左部分有序部分的数据个数,其次还需要让i充当列表的下标
# alist[i] == 8,乱序部分的第一个数据
# alist[i-1] == 3,有序部分的第一个数据
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i += 1
# step_2
i = 2
# alist[i]乱序部分的第一个数据
# alist[i-1]:有序部分的第二个数
while i >= 1:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i -= 1
else:
break
# step_3
for i in range(1, len(alist)+1):
# alist[i]乱序部分的第一个数据
# alist[i-1]:有序部分的第二个数
while i >= 1:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i -= 1
else:
break
#完整的代码
def sort(alist):
for i in range(1,len(alist)):
#alist[i]乱序部分的第一个数据
#alist[i-1]:有序部分的第二个数
while i >= 1:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i -= 1
else:
break
print(alist)

希尔排序(特殊的插入排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#step_1: 增量为1的希尔排序
gap = 1
for i in range(1,len(alist)):
#alist[i]乱序部分的第一个数据
#alist[i-1]:有序部分的第二个数
while i >= 1:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i -= 1
else:
break
print(alist)
##step_1: 实现了增量为gap的希尔排序 == (插入排序)
gap = len(alist)//2
for i in range(gap,len(alist)):
#alist[i]乱序部分的第一个数据
#alist[i-1]:有序部分的第二个数
while i >= 1:
if alist[i] < alist[i-gap]:
alist[i],alist[i-gap] = alist[i-gap],alist[i]
i -= gap
else:
break
print(alist)
##step_3: 实现了增量为gap的希尔排序 == (插入排序)
gap = len(alist)//2
for i in range(gap,len(alist)):
#alist[i]乱序部分的第一个数据
#alist[i-1]:有序部分的第二个数
while i >= 1:
if alist[i] < alist[i-gap]:
alist[i],alist[i-gap] = alist[i-gap],alist[i]
i -= gap
else:
break
print(alist)
#最终代码
def sort(alist):
gap = len(alist)//2
while gap >= 1:
for i in range(gap,len(alist)):
#alist[i]乱序部分的第一个数据
#alist[i-1]:有序部分的第二个数
while i >= 1:
if alist[i] < alist[i-gap]:
alist[i],alist[i-gap] = alist[i-gap],alist[i]
i -= gap
else:
break
gap //= 2
print(alist)

快速排序

  • 设定一个基数,就是原始列表中第0个列表元素的数据值,基数需要存储在一个mid的变量中
  • 设定两个变量一个为low(对应列表第一个数据的下标),一个为high(对应列表最后一个数据的下标)

  • 从右开始偏移high,需要将high指向的数值跟基数进行大小比较,如果high指向的数值>基数,则让high向左偏移一位,继续进行比较,直到high指向的数值小于了基数,则停止high的偏移,将high指向的数值放置在low的位置,然后开始偏移low

  • 从左往右偏移low,如果low指向的数值小于基数,则将low向右偏移一位,如果low指向的数值大于了基数,则停止low的偏移,且将low指向的数值赋值到high的位置,然后偏移high

  • 当low和high重复相遇后,将基数赋值到low或者high指向的位置

  • 将上述操作递归执行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def sort(alist,start,end):
low = start
high = end

if low > high:
return

mid = alist[low]
while low < high:
while low < high:
if alist[high] > mid:#将high向左偏移
high -= 1
else:
alist[low] = alist[high]
break

while low < high:
if alist[low] < mid:#向右移动low
low += 1
else:
alist[high] = alist[low]
break

if low == high:
alist[low] = mid#alist[high] = mid

#将sort的操作作用到基数左侧部分
sort(alist,start,low-1)
#将sort的操作作用的基数右侧部分
sort(alist,high+1,end)

return alist
alist = [6 ,1, 2, 7, 9, 3, 4, 5, 10, 8]
alist = sort(alist,0,len(alist)-1)
print(alist)