Question

分析下面语句段执行的时间复杂度。

Answer 1

问：分析下面语句段执行的时间复杂度。

答：您好亲亲，分析下面语句段执行的时间复杂度如下；时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样: a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a != 0时,时间复杂度就是O(2^n); a=0,b<>0 =>O(n^3); a,b=0,c<>0 =>O(n^2)依此类推

问：分析下面语句段执行的时间复杂度。(1)for (int i=0; i

答：算法的时间复杂度也就是算法的时间度量，记作：T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度。一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。

答：答案是O(n^2)n是循环变量,不同于时间复杂度中的问题规模n.本题出现循环的嵌套,因此时间复杂度为O(n^2)

问：(2)for (int i<0; i

问：(3)i = 1;while(i <= n){i *= 3;}

问：(3)i = 1;while(i <= n){i *= 3;}

问：(4)int i = 1; int k = 0; do{k = k+10*i; ++i;}

答：i++就是i自增1的意思。每次循环后i都会自动加1，直到i>=3时就退出循环。循环几次，如分别是i=0，1，2，3，4，5时执行一次printf("a[%d]=%d\n",i,a[i]);。实例使用了嵌套循环输出2~100之间的素数如下：!/usr/bin/python# -*- coding: UTF-8 -*-i = 2while(i < 100): j = 2while(j j)): if not(i%j): breakj = j + 1if (j > i/j) : print i, " 是素数"i = i + 1

问：是分析他们的复杂度

答：复杂度是log(n)

答：复杂度是O(1)

答：复杂度为O(logn)

答：O(n^2)。