【数据结构】时间复杂度计算集实例详细
另一方面，算法是什么：算法(Algorithm )是对解问题方案的准确完整的描述，是一系列解决问题的明确指令，算法表示用系统的方法描述解决问题的策略机制。
算法特点：一个算法应该具有以下五个重要特征。
“穷性”(Finiteness )算法的穷性意味着该算法可以在执行有限步骤后退出；
确定性(Definiteness )算法的每个步骤都需要准确的定义；
输入(Input )一个算法中，为了描绘运算对象的初始状况，有0个以上的输入。 0个输入意味着算法本身规定了初始条件。
“输出”(Output )一个算法具有一个或多个输出，反映输入数据的加工结果。 没有输出的算法是没有意义的；
由“可行性”(Effectiveness )算法执行的所有计算步骤基本上都可以分解为可行的操作步骤。 也就是说，每个计算步骤都可以在有限时间内完成。 也称为有效性。
二、算法效率测量：计算机可以快速完成运算处理，但实际上对于一定规范的输入，在有限时间内得到要求的输出。 如果算法有缺陷或不符合问题，运行该算法不会解决问题。 不同的算法可能在不同的时间、空间或效率上执行相同的任务。 因此，一个算法的优劣可以用空间复杂度和时间复杂度来衡量。
算法的效率主要通过两个复杂度来评估：评估运行时间复杂度程序所需的时间。 可以估计程序对处理器的使用程度。空间复杂度:评估运行程序所需的存储容量。 可以估算程序的计算机内存使用量。
三、时间复杂度：算法的时间复杂度是指运行算法所需的计算工作量。 相同的问题可以用不同的算法来解决，但一个算法的质量优劣影响算法乃至程序的效率。 算法分析的目的是选择合适的算法，改进算法。 在计算机科学中，算法的时间复杂度是定性描述算法执行时间的函数。 这是关于表示算法输入值的字符串长度的函数。 一般来说，计算机算法是问题规模n的函数f[n]，算法的时间复杂度也为此进行描述。
t(n )=) t(n ) )
不包括这个函数的低次项和初项系数。 使用这种方式时，时间复杂度称为渐近，考察输入值大小无限接近时的情况。 因此，问题规模n越大，算法运行时间的增长率与f(n )的增长率正相关，称为渐进时间复杂度。
由于大o表示法o(f ) n (中f ) n )的值为1、n、logn、n等，因此可以将o ) 1、o ) n、o ) logn、o ) n )分别称为常数阶、线性阶、对数阶和平方阶.
常数阶
//常数级int result=100； //运行程序只运行一次result//system.out.println (' hello！' 执行一次的result； //执行一次以上算法的执行次数的函数为f(n )=3，根据导出较大o次的规则1，每次执行程序时对每个语句执行，因此该算法的时间复杂度保持为o )，称为固定次数
线性阶
//线性阶数for(intI=0； in； I ) system.out.println(result[I]； //执行一次}线性阶数主要分析循环结构运行情况。 由于上述算法循环中的代码执行了n次，所以时间复杂度为o[n]，实际上，for循环中所有时间复杂度为o[1]的语句的总时间复杂度为o[n]。
对数阶
//对数阶数int result=1； while(resultn ) { result=result*2； //可知时间复杂度在o(1)上的代码在result每次乘以2时接近n，在result为n以上时退出循环。 设循环次数为t，则2^T=n，因此T=logn，该算法的时间复杂度为o(logn )。
平方阶
//平方层for(intI=0； in； I ) for(intj=0； jn； I ) system.out.println (result [ I ] [ j ]；//执行一次}}我们知道这是一个循环嵌套语句，内层循环的时间复杂度在说线性阶时已经是o(n )，并且经过外层循环n次时，该算法的
多个复杂度组合：顺序结构
//多个复杂度组合for(intI=0； in； I ) for(intj=0； jn； I ) system.out.println (result [ I ] [ j ]； //执行一次}}for(intI=0
;i<n;i++){ System.out.println(result[i]); //执行一次}对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。
多个复杂度组合：选择结构
// 多个复杂度组合if(flag){ for(int i=0;i<n;i++){ for(int j=0;j<n;i++){ System.out.println(result[i][j]); //执行一次 } }}else{ for(int i=0;i<n;i++){ System.out.println(result[i]); //执行一次 }}对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。
四、例子评注说明：//题目一void fun(int n){ int i,j,x=0; for(i=1;i<n;i++){ for(j=n;j>=i+1;j--){ x++; } }}
【分析】基本运算是语句 x++，假设执行次数为T(n)，则有 ，所以时间复杂度为O()。
//题目二void fun(int n){ int i=0; while(i*i*i<=n){ i++; }}【分析】基本运算是语句 x++，假设执行次数为T(n)，则有 ，即，所以时间复杂度为。
//题目三int m=0,i,j;for(i=1;i<=n;i++){ for(j=1;j<=2*i;j++){ m++; }}【分析】基本运算是语句 m++，假设执行次数为T(n)，则有 ，所以时间复杂度为O()。
//题目四void fun(int n){ int i,k; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ k=1; while(k<=n){ k = 5*k; } } }}【分析】基本运算是语句 k = 5*k;，假设执行时间为T(n)，对于j每循环一次，该语句的执行次数为m，有，即则有 。
掌握一定的解题技巧，所有同类型的就可以迎刃而解了。