绪论

• 常用的渐进复杂度函数 O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2^n)
• 基本循环程序的算法分析,
  1. 基本操作, 认为其时间复杂度是 O(1)
  2. 加法规则,其复杂性是两个分的复杂性之和, T(n)=O(max(T1(n),T2(n)))
  3. 乘法规则(循环结构), T(n)=O(T1(n) x T2(n))
  4. 取最大规则(分支结构),T(n) = O(max(T1(n), T2(n)))
• 一些情况的时间开销
  1. 基本算术运算是常量时间操作, 逻辑预算吗是常量时间运算
  2. 组合操作:复制和切片操作通常是线性时间, list的元素访问和袁术赋值是常量时间的, 列表的最后加入和删除元素效率高,其他地方删除和加入元素效率低
  3. 字符串也应该看做是组合操作, 许多操作不是常量时间的
  4. 创建对象也需要付出空间和时间, 空间和时间代价都与对象大小有关
  5. 构造新结构, 如构造新的list, set等.构造新的空结构是常量时间操作,而构造一个包含n个元素的结构,则至少需要O(n)时间
  6. 一些list操作的效率: 表元素访问和元素修改是常量时间操作, 但一般的加入/删除元素操作(即使只加入一个元素)都是O(n)时间操作
  7. 字典dict操作的效率:最坏时间复杂度是O(n), 但平均复杂度是O(1). 也就是说,一般而言字典效率很高,但是偶然也会出现效率低的情况
• 一些情况的空间开销
  1. 假设程序里建了一个表,而后不断加入元素导致表变得很大,而后不断删除元素,虽然元素变少,但是占用的存储空间并不减少
• 一些不同写法的时间开销

def test1(n):
    lst = []
    for i in range(n*10000):
        lst = lst + [i]
        return lst


def test2(n):
    lst = []
    for i in range(n*10000):
        lst.append(i)
    return lst


def test3(n):
    return [i for i in range(n*10000)]


def test4(n):
    return list(range(n*10000))
#n=10时运行结果
#test1时间3.0994415283203125e-06
#test2时间0.010317087173461914
#test3时间0.0054988861083984375
#test4时间0.00350189208984375

• 一些特别有用的典型数据结构: 集合结构, 序列结构,层次结构,数据结构,图结构.这些数据结构称为结构性的数据结构,因为他们的元素之间要满足某种关系.还有一类是功能性的数据结构,包括栈,队列,优先队列,字典
• python标准函数id取得对象的标识, 内置操作is 和is not 就是通过比较标识的方式怕段是否是同一个对象
• 已知对象标识 访问相应对象的操作可以直接映射到已知地址访问内存单元,这种操作可以在常量时间完成
• 计算机内存里表示数据元素之间的联系有两种基本技术:
  1. 利用数据袁术的存储位置隐式表示, 典型例子就是简单字符串
  2. 吧数据元素之间的联系也看做一种数据,显示的保存在内存中
• python语言中用变量的引用语义, 变量所需的存储空间大小一致,只需要保存一个引用,而c语言是值语义

线性表

• 线性表有两种实现模型, 一个是顺序表,一个是链接表
• 顺序表的实现方式很简单,表中元素顺序存放在一片足够大的连续存储区里,元素之间的逻辑顺序关系通过元素在存储区里的物理位置标示(隐式表示元素间的关系).有两种实现方式,一个是一体式结构,一个是分离式结构.而python里的list实现就是采用分离式技术的动态顺序表3
• list的实现策略:在建立空表时,系统分配一块能容纳8个元素的存储区.插入过程中,如果元素区满了,换一块4倍大的存储区, 但表达到50000时,就变换策略,换存储区时容量加倍
• 采用链接技术实现线性表称为链接表或链表,基本想法如下
  1. 把表中的元素分别存储在一批独立的存储块里
  2. 保证从组成表结构中的任一个节点可找到与其相关的下一个节点
  3. 在前一节点里用链接的方式显式的记录与下一个节点之间的关联
• 单链表:一个单链表由一些具体的表节点构成, 每个节点就是一个对象,有自己的标识, 节点之间通过节点链接建立起单向的顺序联系
• 链表操作复杂度
  1. 创建空表: O(1)
  2. 删除表: O(1)
  3. 判断空表: O(1)
  4. 首端加入元素: O(1)
  5. 尾端加入元素: O(n)
  6. 定位加入元素: O(n)
  7. 首端删除元素: O(1)
  8. 尾端删除元素: O(n)
  9. 定位删除元素: O(n)
  10. 其他删除: O(n)
• r

字符串

• 字符串采用的是一体式顺序表形式
• 匹配算法: 朴素匹配算法, 无回溯匹配算法(KMP算法)

# kmp算法 复杂度O(n)
def matching_kmp(t, p, pnext):
    j, i = 0, 0
    n, m = len(t), len(p)
    while j < n and i <m:
        if i == -1 or t[i] == p[i]:
            j, i = j+1, i+1
        else:
            i = pnext[i]
    if i == m:
        return j - i
    else:
        return -1

• 匹配算法还有一个BM算法,虽然复杂度也是O(n), 但是实际效率要比kmp算法高很多(书上说的)

树 二叉树

• 二叉树: 是一种最简单的树型结构,其特点是树中每个节点至多关联到两个后继节点,另一个特点是关联的后继节点明确的分左右. image
• 1. 不包含任何节点的二叉树称为空树;只包含一个节点的二叉树是一颗单点树
  2. 一颗二叉树的根节点称为该树的子树的父节点
  3. 有些节点没有子节点, 这种节点称为树叶, 树中其他节点称为分支节点,
  4. 一个节点的子节点个数称为该节点的度数, 显然, 树叶节点的度数是0, 分支节点的度数是1或者2
  5. 从一个祖先节点到其任何子孙节点都存在一系列的边,形成从前者到后者的联系,这样一系列首尾相连的边称为树中的一条路径,路径中边的条数称为该路径的长度
  6. 二叉树根的层数为0, 对于位于k层的节点,其子节点是k+1层的元素
  7. 一颗二叉树的高度是树中节点的最大层数
• 二叉树性质
  1. 在非空二叉树第i层中之多有2^i个节点(i>=0)
  2. 高度位h的二叉树至多有2^(h+1) -1 个节点
• 满二叉树:如果二叉树中所有分直接点的度数都是2,则称它位一颗满二叉树
• 完全二叉树: 对于一颗高度为h的二叉树,如果其第0层至第h-1层的节点都满,如果最下一层节点不满,则所有节点在最左边连续排列,空位都在右边,这样的二叉树为完全二叉树
  1. n个节点的完全二叉树高度h, 不大于log2n的最大整数
  2. 如果n个节点的完全二叉树的节点按层次并按从左到右的顺序从0开始编号,
     那么对于任意一个节点i(0<=i<=n-1)都有:
     • 序号为0的是根
     • 对于i>0的,它的父节点是(i-1)/2
     • 若2*i+1<n其左子节点是2*i+1, 否则无左子节点
     • 若2*i+2<n其左子节点是2*i+2, 否则无左子节点
• 1. 深度优先遍历分:先根续,中根序,后根序
  2. 宽度优先遍历又称层次优先遍历,常见的是在每一层里都从左到右逐个访问
• 优先队列:作为缓存结构,优先队列与栈和队列类似考科一将数据元素保存其中,可以访问和弹出,优先队列的特点是存入其中的每项数据都另附有一个数值,表示这个项的优先程度称为其优先级.基于list可以实现优先队列,但无论是顺序表还是链表,效率都不高,所以考虑用堆来实现优先队列.
• 堆: 从结构上看,堆就是节点里存储数据的完全二叉树,但堆中的数据的存储要满足一种特殊的堆序:任一个节点里所存储的数据先于或等于其子节点里的数据
• 堆的应用:堆排序
• 当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
  在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。
  python代码实现

class HTNode(BinTNode):
# BinTNode 是一个自定义的二叉树类
    def  __lt__(self, othernode):
        return self.data < othernode.data

class HuffmanPrioQ(PrioQueue):
    """优先队列类"""
    def number(self);
        return len(self._elems)

def huffmanTree(weights):
    trees= HuffmanPrioQ()
    for w in weights:
        trees.enqueue(HTNode(w)) # 入队列,因为是优先队列,所有弹出时是有顺序的
    while trees.number() > 1:    #如果只剩一个节点,那么跳出循环
        t1 = trees.dequeue()
        t2 = trees.dequeue()
        x = t1.data + t2.data
        trees.enqueue(HTNode(x, t1, t2)
    return trees.dequeue()
```d
# 排序
![640.png](https://img.haomeiwen.com/i9254930/fa57d7e67e3ef259.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
- 插入排序

def insert_sort(lst):
for i in range(1, len(lst)):
current = lst[i] # 当前的值
j -= 1
while j > 0 and current < lst[j]: # 用i 和j比较, 并且每次循环j减1
lst[j+1] = lst[j] # 交换, 将位置j 的数据 放到j+1,
j -= 1
lst[j+1] = current # 当j = 0 ,或者找到了该插入的地方,那么把current插入, lst[j]比current大,所以要插入到j+1的位置

- 冒泡排序

def bubble_sort(numbers):
n = len(numbers)
for i in range(n-1, 0, -1): # j表示每次遍历需要比较的次数，是逐渐减小的
for j in (range(i)):
if numbers[j] > numbers[j+1]:
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]

- 选择排序

def select_sort(lists):
n = len(numbers)
for i in range(n):
minIndex = i
for j in range(i+1, n):
if lists[minIndex] > lists[j]:
minIndex = j
lists[i], lists[minIndex] = lists[minIndex], lists[i]
return lists

- 快速排序

def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)

def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i+1]
return i + 1
111

字典和集合

字典

• 基于顺序表和二分检索实现的字典, 检索速度快O(log n), 但是插入和删除都是O(n),需要连续存储, 所以不适合很大的动态字典
• 以散列表思想实现字典,具体做法是:
  1. 选定一个整数的下标范围(通常以0或者1开始的), 建立一个包括相应元素位置范围的顺序表
  2. 选定一个从实际关键码集合到上述下标范围的适当映射h: 在需要存入关键码为key的数据时, 将其存入表中第h(key)个位置, 遇到以key为关键码检索数据时,直接去找表中第h(key)个位置的元素
     这个h称为散列函数, 也常被称为哈希(hash)函数或杂凑函数,它就是从可能的关键码集合到一个整数区间(下标区间)的映射
• 关键码实现字典时, 所用下标集合通常都远远小于关键码集合的规模,|key| >> |index|, 也就是说: 散列函数h 是从一个大集合到一个小集合的映射
• 冲突是散列表中必然会出现的情况, 负载因子α = (散列表中当时的实际数据项数) / (散列表的基本存储区能容纳的元素个数)

散列函数

• 常见设计散列函数的方法
  1. 用于整数关键码的若干散列方法
     a. 数字分析法
     b. 折叠法
     c. 中平方法
  2. 常见散列函数:
     a. 除余法
     b. 基数转换法
• 解决冲突的方法:
  1. 内消解:
     a. 开地址法: 基本想法是, 唉混呗插入数据并发现冲突时, 设法在基本存储区(顺序表)里为插入的数据项另行安排一个位置,为此需要设计一种系统的且易于计算的位置安排方式,称为探查方式,分为线性探查 和双散列探查

  2. 外消解:
     a. 溢出区方法: 如果冲突较少, 溢出区里的实际数据非常少, 这种方式效果不 错, 当随和溢出区中数据的增长, 字典的性能将趋向线性
     

     b. 桶散列: 另一种可能的做法是数据项不存放在散列表的基本存储区里,二十另外存放. 在散列表里保存对数据项的引用,基于这种想法可以开发出很多不同的设计. 这种设计被称为桶散列, 其中一种最简单的设计 是拉链法 拉链法.jpg

集合

• 定义: 一个集合S就是一些个体的汇集. 如果集合S里有个体e, 就说e是S的一个元素, 或说e数据集合S, 用e∈S表示这个事实. 个体e不属于S用 e∉S表示, 包含所有个体的集合称为全集
• 描述集合的两个方法:
  1. 一种是明确列出其中的所有元素, 这种写法称为集合的外延表示,例如 {1, 3, 5}, 显然, 这种外延表示 还能描述有穷集合
  2. 另一种描述方法时给出集合中的元素应该满足的性质, 这种表示称为集合的描述式, 或者集合的内涵表示, 具体写法是{e|p}, 例如{x+2y | x, y ∈N ʌ x mode y= 3}
• 一个集合中元素的个数称为该集合的基数, 或说该集合的大小