Question

数据结构的作业，麻烦高手帮帮忙

1.2 设n为正整数。试确定下列各程序段中前置以记号@的语句频度：
(1) i=1; k=0;
while (i<=n-1) {
@ k+=10*i;
i++;
}

(2) k=0;
for (i=1;i<=n; i++) {
for (j=i; j<=n; j++)
@ k++;
}

1.3请说明下列算法的时间复杂度。
(1) void sf1 (int n)
{ int i, x=0;
for(i=0; i<5; i++)
for(j=1; j<=n; j++)
x+=2;
}

(2) void sf2 (int n)
{ int i, j, x=1;
for (i=0; i<n; i++)
for(j=0; j<n; j++)
x=x*2;
}

Answer 1

1.2 设n为正整数。试确定下列各程序段中前置以记号@的语句频度：
(1) i=1; k=0;
while (i<=n-1) {
@ k+=10*i; // 1,2 ,3,...,n-1 频度： n-1次
i++;
}

(2) k=0;
for (i=1;i<=n; i++) {
for (j=i; j<=n; j++) i = 1 2 3 ... n
@ k++; j = n n-1 n-2 ...1 频度为 1+ 2+3+...+n = (n+1)n/2
}

1.3请说明下列算法的时间复杂度。
(1) void sf1 (int n)
{ int i, x=0;
for(i=0; i<5; i++) i = 1 2 3 4 5
for(j=1; j<=n; j++) j= n n n n n 频度为5n O(n)
x+=2;
}

(2) void sf2 (int n)
{ int i, j, x=1;
for (i=0; i<n; i++)
for(j=0; j<n; j++) 典型的 O(n^2)
x=x*2;
}