算法
2018-12-24 09:39:07 6 举报AI智能生成
路飞学城第八模块-算法
作者其他创作
大纲/内容
算法进阶
贪心算法
找零问题
背包问题
拼接最大数问题
活动选择问题
动态规划
斐波那契数列
钢条切割问题
递推式
最优子结构
自顶向下递归实现
动态规划解法
重构解
最长公共子序列
欧几里得算法
最大公约数
实现分数计算
RSA加密算法
密码与加密
算法基础
算法概念
时间复杂度
时间复杂度⾼的算法比复杂度低的算法慢。
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
复杂问题的时间复杂度
O(n!) O(2n) O(nn) …
快速判断算法复杂度
确定问题规模n
循环减半过程→logn
k层关于n的循环→nk
复杂情况
根据算法执⾏行行过程判断
空间复杂度
算法使用了几个变量：O(1)
算法使⽤了⻓度为n的⼀维列列表：O(n)
算法使用了了m行n列的二维列表：O(mn)
列表查找
列表查找（线性表查找）
输⼊
列表、待查找元素
输出
元素下标（未找到元素时⼀一般返回None或-1）
内置列表查找函数
index()
顺序查找 (Linear Search)
二分查找 (Binary Searh)
常见排序算法
排序Low B三⼈人组
冒泡排序
时间复杂度：O(n2)
选择排序
时间复杂度：O(n2)
插⼊入排序
时间复杂度：O(n2)
排序NB三人组
快速排序
快速排序的时间复杂度 O(nlogn)
快速排序的问题： 最坏情况 递归
快速排序的问题： 最坏情况 递归
堆排序
⼤根堆
小根堆
堆的向下调整性质
假设根节点的左右⼦树都是堆，但根节点不满⾜堆的性质
可以通过一次向下的调整来将其变成⼀个堆
排序过程
1.建立堆
2.得到堆顶元素，为最大元素
3.去掉堆顶，将堆最后⼀个元素放到堆顶，此时可通过一次调整重新使堆有序
4.堆顶元素为第二大元素。
重复步骤3，直到堆变空。
内置模块
heapq
heapify(x)
heappush(heap,item)
heappop(heap)
topk问题
归并排序
其他排序
希尔排序
计数排序
桶排序
基数排序
数据结构
数据结构介绍
数据结构的分类
线性结构
树结构
图结构
数据结构实例
栈(Stack)
栈的特点
栈的概念
栈的基本操作
队列(Queue)
进行插入的一端称为队尾(rear)，插入动作称为进队或入队
进行删除的一端称为队头(front)，删除动作称为出队
队列的性质
先进先出(First-in, First-out)
双向队列
队列的实现方式
队首指针前进1：front = (front + 1) % MaxSize
队尾指针前进1：rear = (rear + 1) % MaxSize
队空条件：rear == front
队满条件：(rear + 1) % MaxSize == front
链表
创建列表
头插法
尾插法
链表的遍历
链表节点的插入
链表节点的删除
双链表
双链表节点的插入
双链表节点的删除
链表与顺序表比较
哈希表
直接寻址表的缺点
哈希表介绍
哈希冲突
开放寻址法
拉链法
常见哈希函数
除法哈希法
h(k) = k % m
乘法哈希法
h(k) = floor(m*(A*key%1))
全域哈希法
ha,b(k) = ((a*key + b) mod p) mod m a,b=1,2,...,p-1
哈希表的应用
集合与字典
二叉树
链式存储
遍历方式
前序遍历
中序遍历
后序遍历
层次遍历
二叉搜索树
查询
插入
删除
如果要删除的节点是叶子节点：直接删除
如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点
如果要删除的节点有两个孩子：将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点。
AVL树
性质
插入
左旋
右旋
右旋-左旋
左旋-右旋
扩展应用
B树
职业： Data Analyst
0 条评论
下一页
