一、算法
1.算法的时间复杂度
大 O 记法，是描述算法复杂度的符号
O(1)
常数复杂度，最快速的算法。
取数组第 1000000 个元素
字典和集合的存取都是 O(1)
数组的存取是 O(1)
O(logN)
对数复杂度
假设有一个有序数组，以二分法查找
O(n)
线性复杂度
假设有一个数组，以遍历的方式在其中查找元素 最坏情况是全部过一遍
O(nlogn)
求两个数组交集，其中一个是有序数组
A 数组每一个元素都要在 B 数组中进行查找操作
每次查找如果使用二分法则复杂度是 logN
O(N^2)
平方复杂度
求两个无序数组的交集
2.常见问题
"""
常见问题：
O(1)和O(n)区别是什么？
O(1) 是确定的
O(n) 是随着数据规模增长而增长的 最坏情况是全部过一遍 如果第一次就找到了 还是O(n)吗？
我们衡量的是性质 不是特例 以最坏情况来计算 复杂度就意味着查询时间的多少吗? 常数复杂度是直接取第一百万个元素还是按顺序来？
程序中循环的次数，而非真正意义上的时间，因为不同的机器可能执行相同的程序所耗时不同
常数复杂度是说 执行的时间 是确定的 数组的长度不一样，存取元素的时间复杂度是不一样的吗？
数组是一个随机存取的数据结构
无论多长, 存取元素的时间都是确定的, O(1)
"""
# 都是O(1)
# def fun1():
# for i in range(1000000):
# print(i)
# for i in range(1000000):
# print(i*2)
#
# def fun2():
# for i in range(1000000):
# print(i)
# print(i*2)
二、数据结构基础
1.数组
连续的一块内存，存取元素时间是 O(1)，插入、删除是 O(n)
2.链表
像火车，车厢挂车厢
以下标方式读取元素的时间是 O(n)
插入、删除是 O(1)
栈和队列是链表的改良型
栈：先进后出（压弹夹）
队列：先进先出（银行取号排队）
class Node():
def __init__(self, element=None):
self.e = element
self.next = None head = Node()
n1 = Node(111)
n2 = Node(222)
n3 = Node(333)
n1.next = n2
n2.next = n3 head.next = n1 def append(node, element):
"""
我们往 node 的末尾插入一个元素
:param node: 是一个 Node 实例
:param element: 任意类型的元素
"""
n = node
# 这里不应该使用 while n.next: 这样的隐含类型转换来判定
while n.next is not None:
n = n.next
# n 现在是最后一个元素
new_node = Node(element)
n.next = new_node def prepend(head, element):
n = Node(element)
n.next = head.next
head.next = n def pop(head):
"""
pop 是 stack 的两个操作之一
push 入栈
pop 出栈 现在我们有这么 3 个函数
append 添加一个元素到末尾
prepend 添加一个元素到开头
pop 删除并返回末尾的元素 prepend + pop 就实现了 队列 的 入队(enqueue)和出队(dequeue)操作
append + pop 就实现了 栈 的 入栈(push) 和 出栈(pop)操作
"""
tail = head
while tail.next is not None:
tail = tail.next
# 现在 tail 是最后一个元素了
n = head
while n.next is not tail:
n = n.next
# 现在 n 是 tail 之前的元素了
n.next = None
return tail.e def log_list(node):
n = node
s = ''
while n is not None:
s += (str(n.e) + ' > ')
n = n.next
print(s) # log_list(n1)
# append(n1, 'gua')
# log_list(n1)
# prepend(head, 'hello')
# log_list(head)
# print('pop head ', pop(head))
# log_list(head)
链表
""" 队列的特点是「先进先出」，一般有这几个操作 # enqueue 将一个元素存入队列中
# dequeue 将一个元素从队列中取出，并在队列中删除它 # empty 查看栈是否是空的 可以把队列看做排队，银行叫号机就是队列，先取号的先入队，叫号的时候也就先出队 """ # Node类是一个节点，有两个属性，一个存储元素，一个存储指向另一个节点的引用
class Node():
def __init__(self, element=None, next=None):
self.element = element
self.next = next # 这个函数是会在print的时候被自动调用，就是把这个Node显示出来
def __repr__(self):
return str(self.element) class Myqueue():
# 初始化函数，自动被调用
# 初始化Queue()类的时候，它有2个属性，分别指向头尾
def __init__(self):
self.head = Node()
self.tail = self.head # 如果head的next属性为空，则说明队列是空的
def empty(self):
return self.head.next is None # 创建一个node
# 让tail.next指向它
# 让tail指向它，tail现在就是新的队尾了
def enqueue(self, element):
n = Node(element)
self.tail.next = n
self.tail = n # 取出head.next指向的元素，如果队列不是空的，就让head.next指向node.next，这样node就不在队列中了
def dequeue(self):
node = self.head.next
if not self.empty():
self.head.next = node.next
return node # 测试函数
def test():
q = Myqueue() q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4) print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue()) if __name__ == '__main__':
# 运行测试函数
test()
Myqueue
"""
数据结构的核心是，一个结构只有特定的操作，可以实现特定的功能 栈的特点是「先进后出」，一般有这几个操作
# push 将一个元素存入栈中
# pop 将一个元素从栈中取出，并在栈中删除它 # top 将一个元素从栈中取出
# is_empty 查看栈是否是空的 """ # Node类是一个节点，有两个属性，一个存储元素，一个存储指向另一个节点的引用
class Node():
def __init__(self, element=None, next=None):
self.element = element
self.next = next # 这个函数是会在print的时候被自动调用，就是把这个Node显示出来
def __repr__(self):
return str(self.element) class Mystack():
# 初始化函数，自动被调用
# 初始化Stack()类的时候，它有一个head属性，值是一个空的Node
def __init__(self):
self.head = Node() # 如果head的next属性为空，则说明栈是空的
def is_empty(self):
return self.head.next is None # 创建一个node，并让它指向当前head.next指向的元素，再把head.next指向它
def push(self, element):
self.head.next = Node(element, self.head.next) # 取出head.next指向的元素，如果栈不是空的，就让head.next指向node.next，这样node就不在栈中了
def pop(self):
node = self.head.next
if not self.is_empty():
self.head.next = node.next
return node # head.next就是栈里面第一个元素
def top(self):
return self.head.next # 测试函数
def test():
s = Mystack() s.push(1)
s.push(2)
s.push(3)
s.push(4) print(s.pop())
print(s.pop())
print(s.pop())
print(s.pop()) if __name__ == '__main__':
# 运行测试函数
test()
Mystack
3.字典（哈希表 对象 Map）
把字符串转为数字作为下标存储到数组中
字符串转化为数字的算法是 O(1)
所以字典的存取操作都是 O(1)
除非对数据有顺序要求，否则字典永远是最佳选择
字符串转化为数字的算法
1，确定数据规模，这样可以确定容器数组的大小 Size
2，把字符当作 N 进制数字得到结果
'qwe' 被视为 q* 1 + w * 10 + e* 100 得到结果 n
n % Size 作为字符串在数组中的下标
通常 Size 会选一个 素数
3, 当下标冲突(冲突属于叫做碰撞)的时候, 我们有标准解决碰撞的办法
链接法
class HashTable(object):
def __init__(self):
# table 是用来存储数据的数组
# 先让它有 10007 个格子好了
# 上课的时候说过, 这个尺寸最好选素数
# 这样可以得到更为合理的下标分布
self.table_size = 10007
self.table = [0] * self.table_size # 这个魔法方法是用来实现 in not in 语法的
def __contains__(self, item):
return self.has_key(item) def has_key(self, key):
"""
检查一个 key 是否存在, 时间很短, 是 O(1)
如果用 list 来存储, 需要遍历, 时间是 O(n)
"""
index = self._index(key)
# 取元素
v = self.table[index]
if isinstance(v, list):
# 检查是否包含我们要找的 key
for kv in v:
if kv[0] == key:
return True
# 如果得到的是 int 0 说明没找到, 返回 False
# 如果得到的是 list 但是遍历结果没有我们要找的 key 也是没找到
return False def _insert_at_index(self, index, key, value):
# 检查下标处是否是第一次插入数据
v = self.table[index]
data = [key, value]
# 也可以用这个判断 if v == 0:
if isinstance(v, int):
# 如果是第一次, 得到的是 int 0
# 那么就插入一个 list 来存, 以后相同 key 的元素都放这里面
# 注意我们把 key value 作为一个数组保存进去了, 这是因为
# 会出现相同 hash 值的 key
# 这时候就需要比较原始信息来找到相应的数据
self.table[index] = [data]
else:
# 如果不是, 得到的会是 list, 直接 append
self.table[index].append(data) def add(self, key, value):
"""
add 函数往 hashtable 中加入一对元素
我们先只支持字符串当 key； value是uuid生成的随机字符串
"""
# 先计算出下标
index = self._index(key)
# 在下标处插入元素
self._insert_at_index(index, key, value) def get(self, key, default_value=None):
"""
这个和 dict 的 get 函数一样
"""
index = self._index(key)
# 取元素
v = self.table[index]
if isinstance(v, list):
# 检查是否包含我们要找的 key
for kv in v:
if kv[0] == key:
return kv[1]
# 如果得到的是 int 0 说明没找到, 返回 default_value
# 如果得到的是 list 但是遍历结果没有我们要找的 key 也是没找到
return default_value def _index(self, key):
# 先计算出下标
return self._hash(key) % self.table_size def _hash(self, s):
"""
# 输入一个字符串，生成一串对应的数字
下划线开始的函数被我们视为私有函数
但实际上还是可以在外部调用, 这只是一个给自己看的标记
"""
n = 1
f = 1
for i in s:
n += ord(i) * f
f *= 10
return n def test():
import uuid
names = [
'gua',
'xiao',
'name',
'web',
'python',
]
ht = HashTable()
for key in names:
value = uuid.uuid4()
ht.add(key, value)
print('add 元素', key, value)
for key in names:
v = ht.get(key)
print('get 元素', key, v)
print('魔法方法', 'gua' in ht) if __name__ == '__main__':
test()
hash
4.搜索树
class Tree(object):
def __init__(self, element=None):
self.element = element
self.left = None
self.right = None def traversal(self):
"""
树的遍历, 是一个递归操作
"""
print(self.element)
if self.left is not None:
self.left.traversal()
if self.right is not None:
self.right.traversal() def reverse(self):
self.left, self.right = self.right, self.left
if self.left is not None:
self.left.reverse()
if self.right is not None:
self.right.reverse() def test():
# 手动构建二叉树
# 为什么手动这么麻烦呢, 因为一般都是自动生成的
# 这里只需要掌握性质就好
t = Tree(0)
left = Tree(1)
right = Tree(2)
t.left = left
t.right = right
# 遍历
t.traversal() if __name__ == '__main__':
test()
tree