算法分析

HuldaGnodim · 发表于 2022-7-12 09:00

01、概述

定义

算法 != 计算

最早的算法：求最大公因子

算法面向一个问题，而不是一个两个实例。
算法是CS基础的重要主题。—— The Art of Computer Programming 7卷
分析

P：确定图灵机
NP：非确定图灵机多项式时间内能否解决？
单独的复杂性类：图的同构等等...

算法分析：分析而不是实验
正确性

正确性需要严格证明：

复杂性

大数据耗电已经不能忽略电费啦！

虽然分析平均复杂性比较好，但是概率是假设的。

并行：多核、MapReduce

算法设计

暴力遍历
分而治之
图：分支、回溯
随机化方法

02、数学基础

《具体数学》、《算法分析导论》
复杂性函数的阶 —— n是输入的规模

输入的规模、机器、指令集....影响因素
渐进的阶：O、o、theta

增长函数来描述阶

描述的是，增长率的大小。

—— 保留高阶项，忽略低阶。

数据很大时，需要设计亚线性、log算法

最起码

重要的是找到 n0

和式的估计和界限：UNDONE

数列

级数

递归方程：UNDONE

03、分治算法

设计分治算法

例如校园分成一块一块，然后去找卖煎饼果子的，然后排除一些不可能的块，比如教室。

划分、递归调用来求解子问题、合并 —— 如何分、合、尽可能少求解子问题。

例子：大整数算法

例子：最大值、最小值

类似归并排序：

元素选取问题的线性时间算法

中位数：

变为选取第k大的问题：

快速傅立叶变换：

分治法加速计算。

04、动态规划（变化多）

原理

例子：矩阵乘法 —— 计算量和计算顺序有关 —— 找最优的顺序

超大解空间是无法用枚举求出最优解。

递归方程

保存子问题优化解的数据结构 —— 数组
计算顺序（填充顺序）

例子：最长公共子序列 ——

05、贪心法

基本原理

任务安排问题

说明优化解结构

Huffman编码：证明其正确性。

06、搜索策略

大部分事情都能做，但是可能弱一些。
暴力

布尔表达式的可满足性

8-puzzle：

哈密顿环：

BFS、DFS

搜索的优化：爬山策略

启发式

爬山法未必最优解。
Best-First搜索：全局观念

当前所有的节点中最好的。—— 堆

分支界限：剪枝

排除大于可能解的。

07、字符串搜索

概述

Rabin-Karp算法：指纹

KMP算法：最坏也是线性

BMH算法：

		自动登录	找回密码
密码			立即注册