导图社区算法设计与分析

算法设计与分析

算法设计与分析核心要点其中包含了几大基本算法设计思想，可以让我们对算法有一个清晰地整体认识，有助于我们更好的理解算法以及应试。复习时间不够，看这一张图就行了。

编辑于2021-04-04 15:47:59

三日凌空

他的近期作品查看更多>>

算法设计与分析

社区模板帮助中心，点此进入>>

三日凌空

他的近期作品查看更多>>

相似推荐
大纲

互联网9大思维
- 33.7k
- 901
- 2.4k
- 389
MindMaster
组织架构-单商户商城webAPP 思维导图。
- 14.6k
- 3
- 184
- 10
Kacyun
域控上线
- 1.6k
- 162
- 11
- 4
jackrao
python思维导图
- 5.4k
- 521
- 242
- 7
(*^▽^*)
css
- 1.2k
- 1
- 43
- 3
A张舫
CSS
- 3.2k
- 261
- 188
- 33
journey
计算机操作系统思维导图
- 4.2k
- 333
- 203
- 18
journey
计算机组成原理
- 1.5k
- 97
- 70
- 8
journey
IMX6UL(A7)
- 508
- 39
- 5
- 0
Handler XU
考试学情分析系统
- 679
- 50
- 10
- 1
蒋龙

算法

基本概念

排序算法

二分搜索

合并排序元素比较次数和赋值次数，需要辅助数组

选择排序比较次数n(n-1)/2,赋值次数区间

O(N^2)

插入排序

比较次数n-1->n(n-1)/2,赋值次数比它多n-1

给定一个数组，能计算元素比较次数

时间复杂度

最坏O(n^2)

最好O(n)

多种排序算法的时间复杂度

博客

自底向上合并排序

nlogn

比较次数和赋值次数

时间复杂度

计算迭代次数

计算基本运算的频度

Merge中不能以元素比较作为元运算

元运算

不能找到单一的元运算，可以使用多个，只需控制总次数

使用递推关系

空间复杂度

四种关于复杂度的符号

上界O

下界

渐进

复杂度公式

如何计算递推公式求解

数据结构

堆

定义

数组表示的正确规范

标号

从左到右

从上到下

父亲节点不小于子节点的值

几乎完全二叉树

分治

二分搜索

比较次数不超过logn向下取整加1

时间复杂度O(logn)

合并排序

时间复杂度OH(nlogn)

空间OH(n)

分治范式

划分

治理

组合

寻找中项和第K小元素

快速排序

小于在左，大于在右，递归划分

会写划分和递归的整体作用过程

时间复杂度

最坏，已经有序

n^2

最好，每次选的是中项

nlogn

矩阵乘法

公式

矩阵【二维数组】表示和填数据

时间复杂度O[H](n^3)

空间复杂度O[H](n^2)

动态规划

基本

分治和消除冗余

最优子结构

问题的最优解包含子问题的最优解

判断是否是最优子结构

所有点对问题

递推式

算法

时间复杂度 n^3,空间复杂度n^2

三角形切割问题

矩阵链相乘

时间n^2

空间n^3

0-1背包问题

矩阵【二维数组】的含义和表示

优化

棋盘问题