算法分析(渐进分析）

算法分析分为$算法时间复杂度分析$与$算法空间复杂度分析$。一般而言，时间对于我们来说更重要，算法的优化主要也是对时间的优化，而对于空间只要我们的计算机性能较好，对于计算结果影响就不会很大。，下面主要也是对算法一些关于时间复杂度的描述！

1.T(n)函数

当算法时间仅依赖于问题输入规模n，我们可以将其表示为T(n)。

T(n)直接由每一步的操作次数之和相加构成。

下面我们以插入排序的伪代码为例来计算它的T(n)

但是因为当规模变大时，其主要决定作用的就是最高项，所以我们只需要取它的最高项即可，那么久可以表示为 T(n) = n²

2.渐进分析

渐进分析： 就是指忽略掉T(n)的系数与低阶项，仅关注高阶项，用记号θ表示。

下面我们介绍一些渐进记号：

2.1渐进紧确界（θ记号）

先给出它的官方定义：

什么意思呢？就是用θ(g(n))来描述T(n)有一个具体的上界和一个具体的下界，当我们可以找到时，才能进行θ表示。

举例

T(n)=32n2+72−4=θ(n2)T(n) = \frac{3}{2} n^{2} + \frac{7}{2} - 4 = \theta(n^{2})T(n)=23​n2+27​−4=θ(n2)

令n₀ = 2，那么当 n ≥ n₀时，有

寻找下界： 32n2+72−4≥32n2≥n2\frac{3}{2} n^{2} + \frac{7}{2} - 4 ≥ \frac{3}{2} n^{2} ≥ n^{2} 23​n2+27​−4≥23​n2≥n2

寻找上界：32n2+72−4≤32n2+72+n2=6n2\frac{3}{2} n^{2} + \frac{7}{2} - 4 ≤ \frac{3}{2} n^{2} + \frac{7}{2} + n^{2} = 6n^{2} 23​n2+27​−4≤23​n2+27​+n2=6n2

所以存在 c₁ = 1，c₂ = 6，n₀ = 2，使得上式成立，存在渐进紧确界，才可以使用 θ(n²) 表示。

同理可得：

32n5+72n−10=θ(n5)\frac{3}{2} n^{5} + \frac{7}{2}n - 10 = \theta(n^{5}) 23​n5+27​n−10=θ(n5)

n3+n2+n=θ(n3)n^{3} + n^{2} + n = \theta(n^{3}) n3+n2+n=θ(n3)

2.2渐进上界 （O记号）

渐进上界使我们算法分析最常用的方式，因为当我们评价一个算法的优劣时，一般都去找它的最差情况，那么这个就是渐进上界。（大O记法）

先看定义：

举例

$$cosn=O(1)$$

因为 cos n 最大取1，所以是O(1)。

n22−12n=O(n2)\frac{n^{2}}{2} - 12n = O(n^{2}) 2n2​−12n=O(n2)

通过画坐标图来看，很明显 n₂ 更大，所以上界为O(n)。

log7n=log2nlog27=O(log2n)=O(logn)log_{7} n = \frac{log_{2}n}{log_{2}7} = O(log_2{n}) = O(logn) log7​n=log2​7log2​n​=O(log2​n)=O(logn)

使用换底公式进行求解。

对于一般的式子来说我们只需要去掉系数取最高项即可，对于特殊的函数我们才会去找他≤什么。

2.3渐进下界 （Ω记号）

渐进下界就是最好情况，一般不使用它来衡量算法的优劣。

它的定义如下：

举例

n3−2n=Ω(n3)n^{3} - 2n = Ω(n^{3}) n3−2n=Ω(n3)

n2+n=Ω(n2)n^{2} + n = Ω(n^{2}) n2+n=Ω(n2)

同理对于普通的式子，直接去掉系数取最高阶项，遇到复杂的例如调和级数等，我们才会去找他≥什么。

3.常用的换算公式

$$O(f(n))+O(g(n))=O(max\left\{f(n),g(n)\right\})$$

$$O(f(n))+O(g(n))=O(f(n)+g(n))$$

$$O(f(n))\ast O(g(n))=O(f(n)\ast g(n))$$

$$O(c\ast f(n))=O(f(n))$$

$$O(f(n))+\theta (f(n))=\theta (f(n))$$

3.1举例证明

证明：$$O(f(n))+\theta (f(n))=\theta (f(n))$$

设：$$O(f(n))=h(n),\theta (f(n))=g(n)$$
$$注：h(n)和g(n)是不同的函数$$
所以有：
O(f(n))=h(n)=>∃c1,n0>0，∀n≥n0：0≤h(n)≤c1f(n)O(f(n)) = h(n) => \exists c_{1},n_{0}>0， \forall n\ge n_{0}：0\le h(n) \le c_{1}f(n) O(f(n))=h(n)=>∃c1​,n0​>0，∀n≥n0​：0≤h(n)≤c1​f(n)
θ(f(n))=g(n)=>∃c2,c3,n1>0，∀n≥n1：c2f(n)≤g(n)≤c3f(n)\theta(f(n)) = g(n) => \exists c_{2},c_{3},n_{1}>0， \forall n\ge n_{1}：c_{2}f(n)\le g(n) \le c_{3}f(n) θ(f(n))=g(n)=>∃c2​,c3​,n1​>0，∀n≥n1​：c2​f(n)≤g(n)≤c3​f(n)

得出：
∀n≥max{n0,n1}:c2f(n)≤h(n)+g(n)≤max{c1,c3}f(n)\forall n \ge max \left \{ n_{0},n_{1} \right \} :c_{2}f(n) \le h(n)+g(n) \le max \left \{ c_{1},c_{3} \right \}f(n)∀n≥max{n0​,n1​}:c2​f(n)≤h(n)+g(n)≤max{c1​,c3​}f(n)

即：$$O(f(n))+\theta (f(n))=\theta (f(n))得证$$