算法语句计算
Ⅰ 写出1+2+3+…+100的一个算法,并画出流程图和写出算法语句。
(1)算法:
第一步,赋值变量S=0,n=0,i=0
第二步,计算i+1,仍用i表示,计算n+i,仍用n表示.计算S+n,仍用S表示.
第三步,判断i是否大于等于100.若是,输出S,结束算法;若不是,进行第二步.
Ⅱ 这个算法怎么计算
求解算法的时间复杂度的具体步骤是:
⑴找出算法中的基本语句;
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
⑵计算基本语句的执行次数的数量级;
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
⑶用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:
for(i=1;i<=n;i++)x++;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)x++;第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
常见的算法时间复杂度由小到大依次为:
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。
这只能基本的计算时间复杂度,具体的运行还会与硬件有关。