数据结构时间复杂度怎么求？

Question

数据结构时间复杂度怎么求？

Answer 1

简单理解，时间复杂度就是执行语句被调用了多少次。(1)如果只调用了一次，如：x=5;if(x<-4){x=x+4;}else{x=x+3;}在大括号中的内容，只会调用一个语句，那么O(n)=1;(2)如果调用了两次，如：x=5;if(x<-4){x=x+4;}else{x=x+3;}x=x+56;在大括号中的内容，只会调用一个语句，但是在最后，还有一个计算公式要调用语句；总共加起来就是调用2次。那么O(n)=2;（3）用1个FOR循环调用for(x=0;x<n;x++){x=x+1;}x会从0到n-1循环，执行的语句就是将当前x值加入新的x中，总共调用n次；那么O(n)=n;(4）用2个嵌套FOR循环调用for(x=0;x<n;x++){for(y=1;y<=n;y++){x=x+y;}}遇到嵌套循环，可以先将外面的FOR语句中的变量固定为初始值x=0，主要看里面的FOR语句的时间复杂度，很明显，里面语句执行次数是从1到n总共调用n次，O(n)=n；这还只是x=0时的调用。x可以从0到n-1，共n次。每次调用都会执行n次调用y的情况，因此，执行语句x=x+y；总共会调用n*n次。O(n)=n^2。数执行语句的执行次数，就是时间复杂度。注意：(1)找到正确的执行语句。(2)for循环中的初始值和终止值。for(i=0;i<n;i++) i值变化是从0到n-1，共n次。for(i=0;i<=n;i++) i值变化是从0到n，共n+1次。(3)注意for循环的调用顺序，从里面到外面进行的。