题目
【简答题】设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 m=0; for(i=1;i<=n;i++) for (j=2*i; j<=n ;j++) m=m+1;
【简答题】设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 m=0; for(i=1;i<=n;i++) for (j=2*i; j<=n ;j++) m=m+1;
题目解答
答案
O(n 2 ),m 的值等于赋值语句m:=m+1的运行次数,其计算式为
解析
步骤 1：分析外层循环
外层循环从 i=1 到 i=n，每次 i 增加 1。因此，外层循环执行 n 次。
步骤 2：分析内层循环
内层循环从 j=2*i 到 j=n，每次 j 增加 1。因此，内层循环执行 (n - 2*i + 1) 次。
步骤 3：计算 m 的值
m 的值等于内层循环的执行次数之和。因此，m 的值等于：
\[
\sum_{i=1}^{n} (n - 2i + 1)
\]
步骤 4：计算时间复杂度
时间复杂度由外层循环和内层循环的执行次数决定。外层循环执行 n 次，内层循环执行 (n - 2i + 1) 次。因此，时间复杂度为 O(n^2)。
外层循环从 i=1 到 i=n，每次 i 增加 1。因此，外层循环执行 n 次。
步骤 2：分析内层循环
内层循环从 j=2*i 到 j=n，每次 j 增加 1。因此，内层循环执行 (n - 2*i + 1) 次。
步骤 3：计算 m 的值
m 的值等于内层循环的执行次数之和。因此，m 的值等于：
\[
\sum_{i=1}^{n} (n - 2i + 1)
\]
步骤 4：计算时间复杂度
时间复杂度由外层循环和内层循环的执行次数决定。外层循环执行 n 次，内层循环执行 (n - 2i + 1) 次。因此，时间复杂度为 O(n^2)。