数据结构时间复杂度的计算求解

Question

x=91;
y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else
x++;这句为什么是：T(n)=O(1)
i=1;
k=0
while(i<n)
{ k=k+10*i;i++; } 这句又为什么T(n)=n-1
a=0; b=1; ①
for (i=1;i<=n;i++) ②
{ s=a+b; ③
b=a; ④
a=s; ⑤
为什么是2;n；n-1;n-1;n-1;n-1
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次
求解
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
求解

Answer 1

最上面那个 那个程序执行时要么是y-- 要么是x++ 所以循环程序执行次数就是由x 和 y
决定 它是一个常数 所以是T(n)=O(1)

第二个 i=1；循环中i++直到n 而实际上循环体被执行n-1次 所以是 T(n)=n-1、

下一个 2是因为a b各被赋值 还有 n是因为循环从 1 --- n 是等于n的 所以是 n次 循环体内部的 { s=a+b; ③
b=a; ④
a=s; ⑤
被执行n次 要分的很清楚说 for (i=1;i<=n;i++) ② 中的 i<=n 是被执行n+1次 可是 都是总体说他的 执行次数 而简单地只被赋值一次的操作因为是常数 可以忽略 所以总体来说这个 T(n)=n

for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次
总体说 T(n)=n^2 因为只是看循环体被执行几次 这里sum++被执行n^2 次

最后一个计算比较麻烦 应该是log以2为底n 吧 如果没记错追问

for (i=1;i<=n;i++) ②
{ s=a+b; ③
b=a; ④
a=s; ⑤从3以后就不懂了，
最后一段命令不太懂，请您详说好吗？

Answer 2