引子回顾一下最近关于算法的知识。 那当然，首先需要学习时间复杂性的概念及其计算方法。 下面，我们简单介绍一下时间复杂度和一些典型的时间复杂度计算问题。
时间复杂度在算法中取基本操作的执行次数为算法时间复杂度。
一般时间复杂度大小比较关系：
下面给出了几种简单的算法并计算其时间复杂度。
算法案例1公共语音fun (intn ) { int i=1，j=100； wile(In ) { j； i =2； }求出上述算法的时间复杂度。
该算法简单，明显问题规模为n，基本语句为i += 2;。 假设循环进行m次后停止。 在这个时候，我们可以做以下事情。
1 2m K=n。 其中k是常数，可以是0或1以修改结果值。 因为循环结束时，I可能等于n或等于n-1。
上式最终如下。
也就是说，上述算法的时间复杂度为T(n) = O(n)
情况2公共语音Un (Intn ) { int i，j，x=0； for(I=1； i n； I ) for(j=I1； j=n； j () x； }}该算法也很简单，算法规模为n，基本语句为++x;。 通过简单的分析，我们很容易得到：
符合条件的所有I、x； 的执行次数为n - (i 1)1=n - i次。
那么x； 执行次数合计如下。
很明显，上述算法的时间复杂性。
情况3公共语音Un (Intn ) intI=0，s=0； wile(sn ) { i； s =i； }上述算法问题的规模为n，基本语句为++i;和s += i;两句。
对于此问题，假设循环经过m次后结束，s的值为s(m )。 我们很容易得到：
m=1时，s(1)=1； m=2时，为s(2)=s )1)2=1) 2； m=3时，为s(3)=s )2)3=1)2)； 综上所述，循环在经过m次后停止，此时有s(m ) K=n。 k用于修改结果。 也就是说：
我们解开这个，得到了结果：
上面是错误的值，所以我们直接扔掉。 因此，该算法的基本语句执行的次数如下：
很明显，该算法的时间复杂性。
情况4公共语音合并软件(int j，int j ) { int m=0； if(I！=j () m=) Ij )/2； 合并软件(I，m )； 合并排序(m1，j )； }merge(I，j，m )； }我知道以下条件。
调用此方法时，在mergesort(1，n )中调用方法。 merge (方法的时间复杂度为o ) n )。 求出该算法的时间复杂度。
首先，让我们了解一下这个方法。 该方法的实际逻辑可以通过将需要排序的集合二等分并分别排序来理解。
例如，如果i=1，j=20，则表示对包含20个元素的集合进行排序。 mergeSort ) )方法将此集合分为两个集合。 第一个集合的下标从1到10，第二个集合的下标从11到20。 因此，假设mergeSort (方法的基本操作次数为f ) n )，则mergeSort ()方法内部的mergeSort () )方法的基本操作次数为。
有了以上的理解，我们就可以推论：
已知merge (方法的时间复杂度为o ) n )，假设merge )方法的基本操作次数为an。
设mergeSort (方法的基本操作次数为f ) n )。 可以看出以下情况。
；
当时，代入式如下。
；
将公式带入公式，如下所示。
；
另外，当时，代入式如下。
；
将公式带入公式，得到以下内容：
；
同样，我们把……、上面的、、式综合起来，可以得到：
也就是。
然后，可以从mergeSort (方法获得f(1) = O(1) )。
这里，根据式，我们想办法的话，当时有
在此，如果组合两个式子来置换k，则得到mergeSort ()方法的基本操作次数如下。
mergeSort (方法的时间复杂性很明显。
情况5
如上图所示，具有n个元素的顺序表分析了插入和删除一个元素的时间复杂性。
在上面的顺序表中，假设是数组。 插入元素时，必须移动元素的平均个数。 在此，分为两个步骤进行分析。
首先，求出概率。
总是有n个元素，它总共有n + 1个插入点。 如果插入每个位置的可能性相同，则插入每个未知的概率如下：
然后，求出元素的移动个数。
假设在第i个元素之后插入新元素。 如果要在第一个元素之前插入，请在第0个元素之后插入。 (必须将第3358www.Sina.com/个元素后的所有元素向后移动一位。 要移动的元素数为3358ww.Sina
因此，移动元素数量的期望如下：
很明显，平均移动一半元素，插入算法的时间复杂度t[n]=o[n]，删除该算法也同样为o[n]。
总结算法是程序员的内功心法，时间的复杂性是算法学习的基础。 因为与时间复杂性的计算相关的数学知识很多，所以最近打算赶紧复习数学~
见文章1，《数据结构高分笔记》 2016版，率辉主编。