

首页  思维导图  详情



算法

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树

 Collect

Get Started

Dijkstra算法

 Collect

Get Started

控制算法

 Collect

Get Started

算法流程

 Collect

Get Started

机器学习算法分类





0 条评论

下一页