0 Preview

和我组队打过 CTF 的都知道，我脚本能力算是奇葩了，要说不行吧，我总能写出来脚本还都能实现功能。要说行吧。我的程序基本上都是慢的要死，大部分都是遍历查表。

之前师傅看见我的脚本，震惊的无以复加。“复杂度这么高！这玩意儿能跑出来？”
多亏我电脑配置拉满。

刚好在学数据结构和算法的时候，学到了关于算法分析的部分，记一下笔记。

1 算法分析-基本要求

算法分析目的：分析算法的时空效率以便改进算法性能。

评价一个好的算法有以下几个标准:

(1) 正确性 (Correctness ) 算法应满足具体问题需求。
(2) 可使用性 (serviceability) 算法应该很方便的使用。
(3) 可读性 (Readability) 算法应该好读。
(4) 健状性 (Robustness) 算法应具有容错处理。
(5) 效率与低存储量需求算法应执行时间短，占用存储空间小。

我们常说的算法评判名词有：时间复杂度和空间复杂度。
这两个分析方式，都是根据占用资源来分析的：

1.1 评判方法

由于同一种算法在不同的操作系统、编程语言、机器设备上运行的时间都不同，所以很难通过运行时间来评价一个算法。所以通常采用事前估计分析的方法
事前估计分析：撇开上述因素，认为算法的执行时间是问题规模n的函数。

2 时间复杂度分析

一个算法是由控制结构 (顺序、分支和循环三种)和原操作 (指固有数据类型的操作,如+、-、*、/、++和–等)构成的,则算法时间取决于两者的综合效果。

2.1 分析算法的执行时间

🍌语句频度：某语句执行次数称为该语句的语句频度。

一个算法的执行时间可以用该算法的原操作执行次数计算

🍊求出算法所有原操作的执行次数（也称为频度），它是问题规模n 的函数，用T(n)表示。
🍊算法执行时间大致 = 原操作所需的时间×T(n)。所以 T(n)与算法的执行时间成正比。为此用T(n)表示算法的执行时间。
🍊比较不同算法的T(n)大小得出算法执行时间的好坏。

2.2 算法的执行时间用时间复杂度来表示

算法分析不是绝对时间的比较，因此:
算法中执行时间 T(n) 是问题规模 n 的某个函数 f(n) ，记作：T(n) = O(f(n))

记号“O”读作“大O”，若f(n)是正整数n的一个函数,则 T(n) = O(f(n)) 表示存在一个正的常数M,使得当n≥n0 时都满足： |T(n)|≤M|f(n)|
f(n)是T(n)的上界

所以算法的时间复杂度也称作算法的渐近时间复杂度，简称时间复杂度，它表示随问题规模 n 的增>大算法执行时间的增长率和 f(n) 的增长率相同。

也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化 T(n) 的计算，又能比较客观地>反映出当 n 很大时算法的时间性能。

🍎一个没有循环的算法的执行时间与问题规模n无关，记作 O(1) ，也称作常数阶。
🍎一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。
🍎其余常用的算法时间复杂度还有平方阶 O(n2)、立方阶 O(n3)、对数阶O(log2n)、指数阶O(2n)等。

3 空间复杂度分析

空间复杂度：空间复杂度是指算法在计算机内执行时所需存储空间的度量(最大空间)。用于量度一个算法在运行过程中临时占用的存储空间大小。
一般也作为问题规模n的函数，采用数量级形式描述，记作：S(n) = O(g(n))

🍓若一个算法的空间复杂度为O(1)，则称此算法为原地工作或就地工作算法。
🍓估算方法：输入数据所占空间 + 程序所占空间 + 辅助变量所占空间
🍓我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。

4 数据结构+算法=程序

🎏程序设计的本质是对要处理问题选择好的数据结构，同时在此结构上施加一种好的算法。
🎏在选择数据结构时，需要考虑问题的状态描述、所选择的算法等方面。
🎏在选择数据结构时，也要考虑其对算法的影响。

数据结构对算法的影响主要在两方面

（1）数据结构的存储能力
　　数据结构存储能力强、存储信息多＝＞算法将会较好设计（时间少），存储空间大。
　　时间和空间的平衡
（2）定义在数据结构上的操作
　　在数据结构上定义基本操作＝＞算法调用这些基本操作。

🥇选择数据结构需要考虑的几个方面：
（1）数据结构要适应问题的状态描述
（2）数据结构应与所选择的算法相适应
（3）数据结构的选择同时要兼顾程序设计的方便
（4）灵活应用已有知识