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

如题所述

简单理解,时间复杂度就是执行语句被调用了多少次。
(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循环的调用顺序,从里面到外面进行的。
温馨提示:内容为网友见解,仅供参考
第1个回答  2012-12-11
一般的,一次计算那么复杂度为1
循环,则看循环次数,这个可以根据循环条件来,比如for(int i=0;i<10;i++)则复杂度就是10.一般写出O(n) n是循环次数

如果双重循环,则是O(m*n)

看书上的例子吧来自:求助得到的回答本回答被网友采纳
第1个回答  2012-12-11
第2个回答  2018-09-13
那个二次循环的时间自由度错了,x的变化要注意
第3个回答  2019-12-21
结构时间复杂度怎么求?好刀起来了没啊怎么了呢红包
相似回答