He calculated just as men breathe，aseaglessustainthemselvesintheair.- francoisarago
算法对估计的熟练度，就像赞扬大多数学者欧拉一样，必须像呼吸一样计算。
算法分析的主要任务是算法的正确性分析和算法的复杂度分析。 我们主要讨论算法复杂性的分析方法。
一.大o印
在分析算法之前，你必须了解大o标记的作用。 大o标记是算法复杂度分析的利器。
对于特定算法，可以用f(n )表示算法处理数据大小n所需的时间(n2 ) (如图1-1所示，横轴n表示输入大小，纵轴f(n )表示消耗时间)。 ）
(图1-1 )
另一方面，大o是T(N )的前一次渐进。 t(n )=o ) f ) )且有c0，在n 2之后，有t ) n ) c*f ) n )。 下图t ) n )至o ) f(n ) ) :
o(f ) n ) )和t ) n )的比较由图1-2可知
(图1-2 )
与T(N )相比，虽然不是很准确，但o ) f ) n )更简洁，反映了时间的增加趋势。
与大o标记的性质相似，另外，反映t(n )倾向的两种标记分别为(f ) n )、(f ) n ) )，他们分别为t ) n的平均渐近和次渐近。 图1-3:
(图1-3 )
既然我们已经掌握了大o标记的使用，让我们总结一下大o标记所表现出的一般复杂性。
o(1)常数复杂度(包含RAM模型的基本操作) ) ) ) ) )。
o(n )线性复杂度
o(n ) c )多项式复杂度包括o ) n )
O(2^N )指数复杂度)被费解化，随着n迅速增加) ) ) ) ) ) )。
O(N ) c )到o ) n )，是从有效算法到无效算法的分水岭。 note:的许多问题的o(2^n )算法容易设计，但o ) n^c )的算法很难设计，我很乐意设计不出来。
各种复杂性比较：图1-4
(图1-4 )
二.算法分析
为了分析某个特定的算法，在掌握了使用大的o标记这一复杂度分析工具之后，需要知道复杂度分析的方法。
复杂度分析的主要方法：
迭代(级数和递归)递归跟踪递归方程估计验证几类级数用于算法迭代的复杂度分析：
算术级数(与最终项的平方相同的阶数(t(n )=1)2)…n=n )/2=o(n^2) ) ) ) ) ) ) )。
乘方数(比乘方数高一个等级) t(n )=1)2) 2……n )2=n ) n1 ) ) 2n 1)/6=o ) n^3) )。
几何级数(a 1 )与最终项相同次数的t ) n )=a ) 0a ) 2……a(n ) ) a ) n1-1 )/(a-1 )=o ) a ) n ) ) ) )。
收敛级数：1/1/21/2/31//4.1/(n-1 )/n=1-1/n=o(1) ) ) )。
调和级数： h(n )=1)1/2)1/3……1/n=o(Logn ) ) ) ) )。
对数级数： log1log2log3.logn=log(n！ ((o ) ) nlogn ) ) )。
举栗利用算术级数分析循环(迭代)的复杂性：
板栗1 :
for(intI=0； i n； I ) for(intj=0； j n； j )………//其他操作算数级数： nnn……n=n*n=o(n^2) .该循环复杂度为o ) n^2)。
板栗2 :
for(intI=1； i n； i 1 ) for(intj=0； j i； j )……其他操作几何级数：1(2)…2^|_log2(n-1 ) _|=2^[log2n] - 1=O(n ) ) ) ) ) )。
3 .实例分析：
要插入排序复杂度分析：
# includeiostreamusingnamespacestd； #include vector
class project { public : voidxzpx () } { for (inti=1； ia.size (； I ) { key=a[i]； int j=i-1； while(j=0a[j]key ) { a[j 1]=a[j]； j----； } a[j 1]=key； } } project () {} int key； vector inta={ 5，2，4，6，1，3 }； (； int main () { project p； p.xzpx (； for(autoI:p.a ) { cout i endl； } return 0； )算术级数，一眼过去的复杂度为o(n )2)
合并复杂性分析：
# include stdio.husingnamespacestd； voidmerge(inta[ )、int left、int middle、int right )、{ int l_len=middle - left； int r_len=right - middle - 1； int l_a[l_len]； int r_a[r_len]； int i，j，k=left； for(I=0； i=l_len； I ) l_a[i]=a[i left]； for(j=0； j=r_len； j ) r_a[j]=a[j middle 1]； i=0； j=0； while(I=l_lenj=r_len ) if ) l_a[I]r_a[j] ) a[k ]=l_a[i ]； else a[k ]=r_a[j ]； }while(I=L_Len ) a[k ]=l_a[i ]； while(j=r_len ) a[k ]=r_a[j ]； }voidmerge_sort(inta[]，int left，int right ) { int middle； leftright (if ) middle=) left right )/2； merge_sort(a，left，middle )； merge_sort(a，middle 1，right )； merge(a，left，middle，right )； }}int main () inta ) )={ 5，4，3，2，1 }； merge_sort(a，0，4 )； for(intI=0； i5； I ) {printf('%dn '，a[i] )； } return 0； }合并排序递归公式： t(n )=c ) n=1)|2t(n/2 ) cn ) n1 ) ) ) ) ) ) )合并排序递归公式： t(n )=c )|2t(n/2 ) cn ) n1 ) )
递归公式无法求解，需要结合递归跟踪分析：
可以分析，只有合并时才需要时间，每层所有合并都消耗cn，共有log2n 1层。 因此，较耗时的cn(log2n1 )，即，o ) O(n*logn )比插入排序的o ) n^2)更复杂。
我觉得迭代的算法分析很常见。 也很容易分析。
图：学堂在线《数据结构(上)》
转载于：https://www.cn blogs.com/honkeryblogs/p/10581264.html