算法
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) <br>
二分查找 (Binary Searh) <br>
常见排序算法
排序Low B三⼈人组
冒泡排序
时间复杂度：O(n2)
选择排序
时间复杂度：O(n2)
插⼊入排序
时间复杂度：O(n2)
排序NB三人组
快速排序
快速排序的时间复杂度 O(nlogn)<br>快速排序的问题： 最坏情况 递归<br>
堆排序
⼤根堆
小根堆
堆的向下调整性质 <br>
假设根节点的左右⼦树都是堆，但根节点不满⾜堆的性质
可以通过一次向下的调整来将其变成⼀个堆
排序过程
1.建立堆
2.得到堆顶元素，为最大元素
3.去掉堆顶，将堆最后⼀个元素放到堆顶，此时可通过一次调整重新使堆有序
4.堆顶元素为第二大元素。
重复步骤3，直到堆变空。
内置模块 <br>
heapq
heapify(x)
heappush(heap,item)
heappop(heap)
topk问题 <br>
归并排序
其他排序
希尔排序
计数排序
桶排序
基数排序
数据结构
数据结构介绍
数据结构的分类
线性结构
树结构
图结构
数据结构实例
栈(Stack)
栈的特点
栈的概念
栈的基本操作
队列(Queue)
进行插入的一端称为队尾(rear)，插入动作称为进队或入队
进行删除的一端称为队头(front)，删除动作称为出队 <br>
队列的性质
先进先出(First-in, First-out)
双向队列
队列的实现方式
队首指针前进1：front = (front + 1) % MaxSize
队尾指针前进1：rear = (rear + 1) % MaxSize <br>
队空条件：rear == front <br>
队满条件：(rear + 1) % MaxSize == front <br>
链表
创建列表
头插法 <br>
尾插法 <br>
链表的遍历
链表节点的插入
链表节点的删除
双链表
双链表节点的插入
双链表节点的删除
链表与顺序表比较
哈希表
直接寻址表的缺点
哈希表介绍
哈希冲突
开放寻址法
拉链法
常见哈希函数
除法哈希法
h(k) = k % m <br>
乘法哈希法
h(k) = floor(m*(A*key%1)) <br>
全域哈希法
ha,b(k) = ((a*key + b) mod p) mod m a,b=1,2,...,p-1 <br>
哈希表的应用
集合与字典
二叉树
链式存储
遍历方式
前序遍历
中序遍历
后序遍历
层次遍历
二叉搜索树
查询
插入
删除
如果要删除的节点是叶子节点：直接删除
如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点
如果要删除的节点有两个孩子：将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点。
AVL树
性质
插入
左旋
右旋
右旋-左旋
左旋-右旋
扩展应用
B树
职业： Data Analyst
0 条评论
下一页
