题目
分析以下算法的时间复杂度，写出分析过程及结果。void func(int n) {int i, j;for (i = 1; i <= n; i++) {for (j = 1; j <= i; j++) {printf("%d ", i * j);}}}
分析以下算法的时间复杂度，写出分析过程及结果。
void func(int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
printf("%d ", i * j);
}
}
}
题目解答
答案
要分析给定算法的时间复杂度，我们需要仔细观察嵌套循环的执行次数。以下是详细的分析过程：
### 代码分析
```c
void func(int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
printf("%d ", i * j);
}
}
}
```
### 外层循环
外层循环的变量 `i` 从 1 到 `n`，因此外层循环执行 `n` 次。
### 内层循环
内层循环的变量 `j` 从 1 到 `i`，因此内层循环的执行次数取决于 `i` 的值。具体来说：
- 当 `i = 1` 时，内层循环执行 1 次。
- 当 `i = 2` 时，内层循环执行 2 次。
- 当 `i = 3` 时，内层循环执行 3 次。
- ...
- 当 `i = n` 时，内层循环执行 `n` 次。
### 总执行次数
内层循环的总执行次数是所有 `i` 值对应的执行次数之和：
\[ 1 + 2 + 3 + \cdots + n \]
这是一个等差数列的求和问题，其和可以用公式计算：
\[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]
### 时间复杂度
等差数列的和为：
\[ \frac{n(n+1)}{2} = \frac{n^2 + n}{2} \]
在大 O 表示法中，我们只关注最高阶项，并忽略常数系数。因此，时间复杂度为：
\[ O\left(\frac{n^2 + n}{2}\right) = O(n^2) \]
### 结论
该算法的时间复杂度为 $ O(n^2) $。
### 详细解析
1. **外层循环**：执行 `n` 次。
2. **内层循环**：每次外层循环时，内层循环的执行次数分别为 1, 2, 3, ..., n。
3. **总执行次数**：内层循环的总执行次数为等差数列的和，即 $\frac{n(n+1)}{2}$。
4. **时间复杂度**：忽略常数系数和低阶项，最终时间复杂度为 $ O(n^2) $。
因此，该算法的时间复杂度为 $ O(n^2) $。
解析
考查要点：本题主要考查嵌套循环的时间复杂度分析，需要理解如何计算多层循环的总执行次数，并将其转化为大O表示法。
解题核心思路：
- 外层循环次数：外层循环变量
i从1到n，共执行n次。 - 内层循环次数：内层循环变量
j的执行次数与i相关，每次外层循环时，内层循环执行i次。 - 总执行次数：将所有内层循环的次数相加，转化为数学表达式并简化。
- 时间复杂度：根据简化后的表达式，提取最高阶项，忽略常数系数，得到最终时间复杂度。
破题关键点：
- 等差数列求和：内层循环总次数为
1 + 2 + 3 + ... + n，需用等差数列公式计算。 - 大O表示法：仅保留最高阶项，忽略低阶项和常数系数。
代码分析
函数func包含两层嵌套循环：
- 外层循环：
i从1到n，共执行n次。 - 内层循环：
j从1到i，每次外层循环时，内层循环执行i次。
总执行次数计算
内层循环的总执行次数为：
$\sum_{i=1}^{n} i = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$
展开后为：
$\frac{n^2 + n}{2}$
时间复杂度分析
在大O表示法中，最高阶项为n²，因此时间复杂度为：
$O\left(\frac{n^2 + n}{2}\right) = O(n^2)$