高级算法设计与分析（一） -- 算法引论

系列文章目录

高级算法设计与分析（一） -- 算法引论

高级算法设计与分析（二） -- 递归与分治策略

高级算法设计与分析（三） -- 动态规划

未完待续【

高级算法设计与分析（四） -- 贪心算法

高级算法设计与分析（五） -- 回溯法

高级算法设计与分析（六） -- 分支限界法

高级算法设计与分析（七） -- 概率算法

高级算法设计与分析（八） -- NP完全性理论

】

高级算法设计与分析（九） -- 总结

---

目录

系列文章目录

前言

一、算法与程序

1、算法

2、程序

3、思算法的基本特征

3.1、输入（0~N个）

3.2、输出（1~N个）

3.3、确定性

3.4、有限性

二、表达算法的抽象机制

1、数据

2、运算

3、算法用程序描述的基本方法

三、算法的复杂性分析

1、时间复杂度与空间复杂度（对资源的消耗）

2、复杂度的计算

3、复杂性渐进态（次数最高的那一项）

3.1、O（order）的定义

3.1.1、O的运算规则

3.3.2、O的实质

3.3.3、O的理解

3.2、Ω和θ

习题

---

前言

tips：鉴于本人写字如画符，就不出视频教程了，如实在有需要，请在文章下方留言。当然，文章有任何问题，也请留言，谢谢！

这个系列用另一种形式，把习题放在最下面，看看好用不。

本系列文章最后一文会进行简要全部总结，以及思维导图放在最后一篇文章最下面，请自行获取。

---

一、算法与程序

1、算法

指解决问题的方法或过程。

2、程序

算法用某种程序设计语言的具体实现。

3、思算法的基本特征

3.1、输入（0~N个）

0个输入的算法不具有通用性，但有用，如计算Π

3.2、输出（1~N个）

不可能没有输出（结果）

3.3、确定性

指令清晰、无歧义，但并不表示每次运行算法都会获得同样结果，如并行算法

3.4、有限性

每条指令执行次数、执行每条指令时间均有限，因此算法所需总时间也有限

二、表达算法的抽象机制

1、数据

基本数据：布尔值、字符、整数、浮点数等。矩阵、集合等较复杂数据均由基本数据构成。

2、运算

逻辑运算、关系运算、矩阵运算等
a=1; b=2; a>b
Matlab(Matrix laboratory)就是以矩阵运算为基础

3、算法用程序描述的基本方法

自顶向下，逐步求精

三、算法的复杂性分析

1、时间复杂度与空间复杂度
（对资源的消耗）

记法：T = T(N, I, A)或T(A) = T(N, I)或T=T(N, I)

含义：算法A的时间复杂度由问题规模(N)和输入(I)确定

2、复杂度的计算

3、复杂性渐进态
（次数最高的那一项）

3.1、O（order）的定义

3.1.1、O的运算规则

3.3.2、O的实质

3.3.3、O的理解

3.2、Ω和θ

O：不高于
Ω：不低于
θ：等于（阶数相等）

O：不高于 ? ? ? ? ? ? ? ? ? o：小于
Ω：不低于 ? ? ? ? ? ? ? ? ? ω：大于
θ：等于（阶数相等）

---

习题

topic（1）：

！！！ 20n>n^(2/3)

topic（2）：

topic（3）：

topic（4）：