1.算法复杂度的度量
常见函数的大O表示法
1.1 对于List
Big-O Efficiency of Python List Operators
1.2 对于字典
字典操作效率表（大O表示法）
2. 基本数据结构类型
2.1 栈
栈的排序原则：LIFO 后进先出
简单的栈操作
Stack()：创建一个新的空栈。它不需要参数，并返回一个空栈。
Push(item)：将新项添加到堆栈的顶部。它需要参数 item 并且没有返回值。
pop()：从栈顶删除项目。它不需要参数,返回 item。栈被修改。
peek()：返回栈顶的项，不删除它。它不需要参数。堆栈不被修改。
isEmpty()：测试看栈是否为空。它不需要参数，返回一个布尔值。
size()：返回栈的项目数。它不需要参数，返回一个整数。
2.2 队列(Queue)
先进先出（FIFO）
简单队列
队列的基本操作：
● Queue()创建一个空队列对象，无需参数，返回空的队列；
● enqueue(item)将数据项添加到队尾，无返回值；
● dequeue()从队首移除数据项，无需参数，返回值为队首数据项；
● isEmpty()测试是否为空队列，无需参数，返回值为布尔值；
● size()返回队列中的数据项的个数，无需参数。
简单队列操作
在Python中实现队列：
Class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self, item):
self.items.pop()
def size(self):
return len(self.items)
q = Queue()
q.enqueue('dog')
q.enqueue(4)
print(q.size())
热土豆问题的模拟实现：
from pythonds.basic.queue import Queue
def hotPotato(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:
for i in range(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
print(hotPotato(["Alice", "Bob", "Cindy", "David", "Ella", "France"], 7))
打印任务的实现：
import random
from pythonds.basic.queue import Queue
class Printer:
def __init__(self, ppm):
self.pagerate = ppm
self.currentTask = None
self.timeRemaining = 0
def tick(self):
if self.currentTask != None:
self.timeRemaining = self.timeRemaining - 1
if self.timeRemaining <= 0:
self.currentTask = None
def busy(self):
if self.currentTask != None:
return True
else:
return False
def startNext(self, newtask):
self.currentTask = newtask
self.timeRemaining = newtask.getPages() * 60 / self.pagerate
class Task:
def __init__(self, time):
self.timestamp = time
self.pages = random.randrange(1, 21)
def getStamp(self):
return self.timestamp
def getPages(self):
return self.pages
def waitTime(self, currenttime):
return currenttime - self.timestamp
def simulation(numSeconds, pagesPerMinute):
labprinter = Printer(pagesPerMinute)
printQueue = Queue()
waitingtimes = []
for currentSecond in range(numSeconds):
if newPrintTask():
task = Task(currentSecond)
printQueue.enqueue(task)
if (not labprinter.busy()) and (not printQueue.isEmpty()):
nexttask = printQueue.dequeue()
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.startNext(nexttask)
labprinter.tick()
averageWait = sum(waitingtimes) / len(waitingtimes)
print("Average Wait %6.2f secs %3d tasks remaining." % (averageWait, printQueue.size()))
def newPrintTask():
# 产生一个新的打印任务的概率
num = random.randrange(1, 181)
if num == 180:
return True
else:
return False
for i in range(10):
simulation(3600, 5)
2.2 双端队列(deque 或 double-ended queue)
元素可以从两端插入，也可以从两端删除。 可以说，
双端队列这种混合的线性数据结构拥有栈和队列各自拥有的所有功能
双端队列
双端队列的基本操作：
- Deque() 创建一个空双端队列，无参数，返回值为 Deque 对象。
- addFront(item) 在队首插入一个元素，参数为待插入元素，无返回值。
- addRear(item) 在队尾插入一个元素，参数为待插入元素，无返回值
- removeFront() 在队首移除一个元素，无参数，返回值为该元素。双端队列会被改变。
- removeRear() 在队尾移除一个元素，无参数，返回值为该元素。双端队列会被改变。
- isEmpty() 判断双端队列是否为空，无参数，返回布尔值。
- size() 返回双端队列中数据项的个数，无参数，返回值为整型数值
双端队列的操作
python实现双端队列：
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
self.items.pop()
def removeRear(self):
self.items.pop(0)
def size(self):
return len(self.items)
回文判断函数的实现：
from pythonds.basic.deque import Deque
def palchecker(aString):
chardeque = Deque()
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
2.3 无序列表
无序列表是一些元素的集合，每个元素拥有一个与其它元素不同的相对位置。
常用的方法有：
- list() 创建一个新的空列表。它不需要参数，而返回一个空列表。
- add(item) 将新项添加到列表，没有返回值。假设元素不在列表中。
- remove(item) 从列表中删除元素。需要一个参数，并会修改列表。此处假设元
素在列表中。 - search(item) 搜索列表中的元素。需要一个参数，并返回一个布尔值。
- isEmpty() 判断列表是否为空。不需要参数，并返回一个布尔值。
- size() 返回列表的元素数。不需要参数，并返回一个整数。
- append(item) 在列表末端添加一个新的元素。它需要一个参数，没有返回值。
- index(item) 返回元素在列表中的位置。它需要一个参数，并返回位置索引值。
- insert(pos,item) 在指定的位置添加一个新元素。它需要两个参数，没有返回值。
- pop() 从列表末端移除一个元素并返回它。它不需要参数，返回一个元素。假设列表至少有一个元素。
- pop(pos) 从指定的位置移除列表元素并返回它。它需要一个位置参数，并返回一个元素。假设该元素在列表中。
为了实现无序列表，我们将构建一个链表
需要注意的是，该列表的第一项的位置必须被明确指出。一旦我们知道第一项是什么，第一项就可以告诉我们第二项是什么，以此类推。从外部指向的第一项通常被称为链表的头。同样地，链表的最后一项需要告诉我们有没有下一个项目。
用链表实现的基本模块是节点。每个节点对象必须持有至少两条信息。首先，节点必须包含列表元素本身。我们将这称为该节点的“数据区”（data field）。此外，每个节点必须保持到下一个节点的引用。
python实现节点：
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
python实现无序列表：
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
# 要移除的是第一个元素的情况
if previous == None:
self.head = current.getNext()
# 要移除的是最后一个元素的情况
elif current == None:
previous.setNext(None)
else:
previous.setNext(current.getNext())
def append(self, item):
current = self.head
previous = None
# 列表为空时
if current == None:
last_item = Node(item)
last_item.setNext(self.head)
self.head = last_item
else:
while current != None:
previous = current
current = current.getNext()
last_item = Node(item)
previous.setNext(last_item)
def insert(self, index, item):
current = self.head
previous = None
count = 0
# 先对index有没有超过list长度进行判断
if index > self.size():
raise IndexError
else:
while count != index:
count += 1
previous = current
current = current.getNext()
# 说明是在开头位置插入元素
if previous == None:
insert_item = Node(item)
insert_item.setNext(self.head)
self.head = insert_item
# 说明是在list结尾插入元素
else:
insert_item = Node(item)
insert_item.setNext(current)
previous.setNext(insert_item)
def index(self, item):
current = self.head
count = 0
found_flag = True
while current.getData() != item:
count += 1
current = current.getNext()
if current == None:
found_flag = False
break
if found_flag:
return count
else:
return None
def pop(self, index=None):
if index == None:
index = self.size() - 1
current = self.head
count = 0
previous = None
# 先判断index是否超出范围
if (index >= 0 and index > self.size() - 1) or (index < 0 and index + self.size() > self.size()):
raise IndexError
else:
if index >= 0:
while index != count:
count += 1
previous = current
current = current.getNext()
else:
while index + self.size() != count:
count += 1
previous = current
current = current.getNext()
# 说明删除的是第一个元素
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
return current
mylist = UnorderedList()
mylist.append(12)
mylist.insert(0, 2)
mylist.append(15)
mylist.pop()
2.4 有序列表
有序列表的方法：
- OrderedList()：创建一个新的空有序列表。它返回一个空有序列表并且不需要传递任何参数。
- add(item):在保持原有顺序的情况下向列表中添加一个新的元素，新的元素作为参数传递进函数而函数无返回值。假设列表中原先并不存在这个元素。
- remove(item):从列表中删除某个元素。欲删除的元素作为参数，并且会修改原列表。假设原列表中存在欲删除的元素。
- search(item)：在列表中搜索某个元素，被搜索元素作为参数，返回一个布尔值。
- isEmpty()：测试列表是否为空，不需要输入参数并且其返回一个布尔值。
- size()：返回列表中元素的数量。不需要参数，返回一个整数。
- index(item)：返回元素在列表中的位置。需要被搜索的元素作为参数输入，返回此元素的索引值。假设这个元素在列表中。
- pop()：删除并返回列表中的最后一项。不需要参数，返回删除的元素。假设列表中至少有一个元素。
- pop(pos)：删除并返回索引 pos 指定项。需要被删除元素的索引值作为参数，并且返回这个元素。假设该元素在列表中
python实现有序列表：
class OrderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self, item):
current = self.head
previous = None
stop = False
while current is not None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous is None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
# 要移除的是第一个元素的情况
if previous == None:
self.head = current.getNext()
# 要移除的是最后一个元素的情况
elif current == None:
previous.setNext(None)
else:
previous.setNext(current.getNext())
def append(self, item):
current = self.head
previous = None
# 列表为空时
if current == None:
last_item = Node(item)
last_item.setNext(self.head)
self.head = last_item
else:
while current != None:
previous = current
current = current.getNext()
last_item = Node(item)
previous.setNext(last_item)
def insert(self, index, item):
current = self.head
previous = None
count = 0
# 先对index有没有超过list长度进行判断
if index > self.size():
raise IndexError
else:
while count != index:
count += 1
previous = current
current = current.getNext()
# 说明是在开头位置插入元素
if previous == None:
insert_item = Node(item)
insert_item.setNext(self.head)
self.head = insert_item
# 说明是在list结尾插入元素
else:
insert_item = Node(item)
insert_item.setNext(current)
previous.setNext(insert_item)
def index(self, item):
current = self.head
count = 0
found_flag = True
while current.getData() != item:
count += 1
current = current.getNext()
if current == None:
found_flag = False
break
if found_flag:
return count
else:
return None
def pop(self, index=None):
if index == None:
index = self.size() - 1
current = self.head
count = 0
previous = None
# 先判断index是否超出范围
if (index >= 0 and index > self.size() - 1) or (index < 0 and index + self.size() > self.size()):
raise IndexError
else:
if index >= 0:
while index != count:
count += 1
previous = current
current = current.getNext()
else:
while index + self.size() != count:
count += 1
previous = current
current = current.getNext()
# 说明删除的是第一个元素
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
return current
2.5 链表的算法分析
当分析链表方法的复杂度时，我们应该考虑它们是否需要遍历链表。考虑一个有 n 个节点的链表， isEmpty 方法复杂度是 O（1），因为它只需要检查链表的头指针是否为 None。对于方法 size，则总需要 n 个步骤，因为除了遍历整个链表以外，没有办法知道链表的节点数。因此， size 方法的复杂度是 O（n）。无序列表的 add 方法的复杂度是 O（1），因为我们永远只需要在链表的头部简单地添加一个新的节点。但是， search、 remove 和在有序列表中的 add 方法，需要遍历。尽管在平均情况下，它们可能只需要遍历一半的节点，但这些方法的复杂度都是 O(n)，因为在最糟糕的情况下需要遍历整个链表。
你可能还注意到， 这些方法的实现性能与 Python 的内置列表 list 不同，这表明 Python 中的 list不是这么实现的。实际上， Python 中的列表的实现是基于数组的
2.6 小结
线性数据结构以有序的方式维持它们的数据。
栈（Stack）是具有后进先出（LIFO）特性的有序的简单数据结构。
栈（Stack）的基本操作是 push， pop 和 isEmpty。
队列（Queue）是具有先进先出（FIFO）特性的有序的简单数据结构。
队列（Queue）的基本操作是 enqueue,dequeue 和 isEmpty。
前缀表达式，中缀表达式和后缀表达式都是书写表达式的方式。
栈（Stacks）对于设计算法并求值以及转化表达式非常有效。
栈（Stacks）具有反转的特性。
队列（Queue）可以帮助构建时序仿真。
模拟实验使用随机数生成器来创建一个真实的环境从而使我们回答“假设”类型的问题。
双端队列（Deque）是允许像栈和队列一样的混合行为的数据结构。
双端队列（Deque）的基本操作是 addFront, addRear, removeFront, removeRear 和 isEmpty。
列表（List）是具有相对位置的元素的集合。
链表的实现保持逻辑顺序而不要求数据项依次存放在连续的存储空间。
对链表表头的修改是一种特殊情况
3. 递归
3.1递归三大定理：
- 递归算法必须有个基本结束条件
- 递归算法必须改变自己的状态并向基本结束条件演进
- 递归算法必须递归地调用自身
将 整 数 转 化 成 任 意 进 制 表 示 的 字 符 串 形 式：
def to_str(n, base):
convert_string = '0123456789ABCDEF'
if n < base:
return convert_string[n]
else:
return to_str(n // base, base) + convert_string[n % base]
print(to_str(10, 2))
栈帧：实现递归
from pythonds.basic.stack import Stack
r_stack = Stack()
def to_str(n, base):
convert_string = '0123456789ABCDEF'
while n > 0:
if n < base:
r_stack.push(convert_string[n])
else:
r_stack.push(convert_string[n % base])
n = n // base
res = ""
while not r_stack.isEmpty():
res = res + str(r_stack.pop())
return res
print(to_str(1453, 16))
3.2 图示递归：
python绘制递归圆形
import turtle
myTurtle = turtle.Turtle()
myWin = turtle.Screen()
def drawSprial(myTurtle, radius, angle):
if angle > 0:
myTurtle.circle(radius)
myTurtle.left(30)
drawSprial(myTurtle, radius, angle - 30)
drawSprial(myTurtle, 100, 360)
myWin.exitonclick()
python绘制分形树
import turtle
def tree(branchLen, t):
if branchLen > 5:
t.forward(branchLen)
# print(1, branchLen)
t.right(20)
tree(branchLen - 15, t)
# print(2, branchLen)
t.left(40)
tree(branchLen - 10, t)
# print(3, branchLen)
t.right(20)
t.backward(branchLen)
def main():
t = turtle.Turtle()
myWin = turtle.Screen()
t.left(90)
t.up()
t.backward(100)
t.down()
t.color("green")
tree(75, t)
myWin.exitonclick()
main()
4. 搜索与排序
4.1搜索
4.1.1顺序搜索
python实现顺序搜索
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos += 1
return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 0))
有序列表的顺序搜索
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos += 1
return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 0))
4.1.2 二分法搜索
二分法搜索一个有序表
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(testlist, 42))
递归实现二分法：
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(testlist, 42))
二分法搜索的复杂度是O(log(n))，因为比对的次数为 n/2^i=1，解得i = log(n)。
即使二分搜索通常比顺序搜索要好，值得注意的是，对于较小的n值，排序所附加的消耗可能是不值得的。事实上，我们应当一致考虑进行额外的排序工作来得到搜索优势是否是有效开销。如果我们可以排序一次然后搜索许多次，排序开销并不是那么显著。然而，对于大列表，哪怕是一次排序的消耗也可能是巨大的，从一开始简单执行顺序搜索也许是最好的选择。
4.1.3 散列
我们将尝试进一步建立一种新的数据结构，基于他的搜索算法的时间复杂度为O(1)。这个概念被称为散列。
散列表的每一个位置叫做槽，能够存放一个数据项，并以从0开始递增的整数命名。在初始条件下，散列表中是没有任何数据的，即每个槽都是空的。我们可以利用列表实现一个散列表，它的每一个元素都被初始化为None。
某个数据项与在散列表中存储它的槽之间的映射叫做散列函数。将数据传入散列函数计算得出的是这个数据储存在散列表中槽的位置。一般地，我们把槽被占据的比例叫做负载因子，** λ= 数据项个数 / 散列表的大小。
当然，当散列函数计算出两个甚至多个数据需要存储在同一个槽中，这表示散列函数不合适，这种情况被称为冲突。对于一组给定的数据项，如果一个散列函数可以将每一个数据项都映射到不同的槽中，那么这样的散列函数叫做完美散列函数。但是，如果给定的数据项是任意的，那么就没有一种系统化的方法来构造一个完美的散列函数。
4.2 排序
4.2.1 冒泡排序
python实现冒泡排序：(时间复杂度为O(n^2))
def bubbleSort1(alist):
for x_idx in range(len(alist) - 1, 0, -1):
for y_idx in range(x_idx):
# 如果前面的数据比后面大就往后排
if alist[y_idx] > alist[y_idx + 1]:
temp = alist[y_idx]
alist[y_idx] = alist[y_idx + 1]
alist[y_idx + 1] = temp
def bubbleSort2(alist):
passnum = len(alist) - 1
while passnum > 0:
for i in range(passnum):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
passnum -= 1
testlist = [1, 4, 5, 23, 6, 435, 14, 61, 2354, 512, 4]
bubbleSort1(testlist)
print(testlist)
局限性：
因为冒泡排序必须要在最终位置找到之前不断交换数据项，所以它经常被认为是最低效的排序方法。我们可以改良冒泡排序，使其在已知列表排好的情况下提前结束。这就是说，如果一个列表只需要几次遍历就可排好，冒泡排序就占有优势：它可以在发现列表已排好时立刻结束。这就是改良版冒泡排序。它通常被称作“短路冒泡排序”。
def shortBubbleSort(alist):
exchanges = True
passnum = len(alist) - 1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i] > alist[i + 1]:
exchanges = True
alist[i], alist[i + 1] = alist[i + 1], alist[i]
passnum = passnum - 1
alist = [1, 45, 65, 3, 1, 3, 6, 7, 12, 457, 2, 45, 234]
shortBubbleSort(alist)
print(alist)
三种方法效率对比
