Question

s=0; for(i=1;i<n;i++) for(j=n;j>=i;j--） s=s+i+j 求s=s+i+j的频度和程序的时间复杂度

Answer 1

s=0;
for(i=1;i<n;i++) //i从1变到n-1
for(j=n;j>=i;j--）//对每个i，j从n变到i，次数是(n-i+1)
s=s+i+j

当i=1时，j的变化次数，即语句的执行次数是n;
当i=2时，次数是n-1;
当i=3时，次数是n-2;
...
当i=n-1时，次数是2;
所以，s=s+i+j的频度是
n+(n-1)+(n-2)+...+2=(n-1)(n-2)/2
程序的时间复杂度是O(n^2)
注：n^2是n的平方

Answer 2

你好，频度和程序的时间复杂度是什么