算法基础概述

算法的基本性质

算法是每一步经过精确定义的，能够通过有限步骤计算出确定结果的运算过程，算法有0个或多个输入，取决于算法的问题规模，一定有输出，没有输出的算法没有意义。

算法时间复杂度的估量

考虑三种情况
Tmax(N )、Tmin(N)和Tavg(N )
最好和平均情况下的时间复杂度是认为的添加了部分理想假设计算出来的，根据实践，最有实际价值的是Tmax(N)，最差情况。

为了分析方便，我们一般取T(n)=O(f(n))，表示存在某一常数C，使得对所有n≥1，都有T(n)≤C×f(n)。
证明：例：若T(n)=5n3+3n+12，则T(n)=O(n3)。
证：5n3+3n+12≤5n3+3 n3+12 n3=20n3，对所有n≥1成立，取C=20，则有T(n)≤C×n3 <证毕>

复杂渐进态
设T(N)是关于算法A的复杂性函数，当N→∞，(T(N )-T’(N ))/T(N ) → 0，那么T’(N)是T(N)当N→∞时的渐近性态，当N足够大时，我们用T(N)的渐进态函数表示算法A的时间复杂度。

综上，当输入规模足够时候，我们考虑算法的T'(N)阶就行了。

渐进符号O的定义：
f(n)=O(g(n))当且仅当存在正的常数c和n0， 使得对于所有的n>=n0，有f(n)<=cg(n)。
函数f至多是函数g的c倍，除非n<n0 。即是说，当充分大时，g是f的一个上界函数，在相差一个非零常数倍的情况下。
注意：
用来作比较的函数g(n)应该尽量接近所考虑的函数f(n).
3n+2=O(n2) 松散的界限；3n+2=O(n) 较好的界限
f(n)=O(g(n))不能写成g(n)=O(f(n)).
对于函数f(n)和g(n),如果极限limn->∞(f(n)/g(n))存在，则f(n) = O(g(n));
举例：

image.png

符号的Ω定义：
f(n)= Ω(g(n))当且仅当存在正的常数c和n0， 使得对于所有的n>=n0，有f(n)>=cg(n)。
函数f至少是函数g的c倍，除非n<n0 。即是说，当充分大时，g是f的一个下界函数，在相差一个非零常数倍的情况下。

符号的θ定义：
f(n)= θ(g(n))当且仅当存在正的常数c1,c2和n0， 使得对于所有的n>=n0，有c1g(n)<=f(n)<=c2g(n)。
函数f介于函数g的c1、c2倍之间，除非n<n0 。即是说，当充分大时，g既是f的下界，又是f的上界。

image.png

举例子

image.png
性质
image.png