分析下列程序段的时间复杂度： x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++;

这段程序的时间复杂度为 $O(n^2)$。

原因如下：

该程序段中有两个嵌套的循环，外层循环的次数为 $n-1$，内层循环的次数为 $n-i$，因此总共的循环次数为：

$$
\sum\limits_{i=1}^{n-1}{(n-i)}=\sum\limits_{j=1}^{n-1}j=\frac{(n-1)\times n}{2}=O(n^2)
$$

在循环体内部，只有一条语句，即 x++，该语句的时间复杂度为 $O(1)$，因此总时间复杂度为 $O(n^2)$。

最后，程序将 x 的值赋给了某个变量，这一步不会影响时间复杂度。

相关问题

分析下列程序段的时间复杂度： s=0; for i=0; i<n; i++) for(j=0; j<n; j++) s+=B[i][j]; sum=s;

这段程序的时间复杂度为 $O(n^2)$。

原因如下：

该程序段中有两个嵌套的循环，外层循环的次数为 n，内层循环的次数也为 n，因此总共的循环次数为 $n\times n=n^2$。

在循环体内部，只有一条语句，即 s+=B[i][j]，该语句的时间复杂度为 $O(1)$，因此总时间复杂度为 $O(n^2)$。

最后，程序将 s 的值赋给了 sum，这一步不会影响时间复杂度。

给出下列程序片段的时间复杂度分析 sum = 0; if (EVEN(n)) for (i = 0; i < n; i++) sum ++; else sum = sum +n;

时间复杂度分析：

1. 对于第一行代码，赋值操作的时间复杂度为 O(1)。

2. 对于第二行代码，判断一个数是否为偶数的时间复杂度为 O(1)。

3. 对于第三行代码，如果 n 是偶数，则会执行 for 循环，循环次数为 n/2，时间复杂度为 O(n/2)，同时循环内部只有一次加法操作，时间复杂度为 O(1)。因此，总时间复杂度为 O(n/2)。

4. 对于第四行代码，如果 n 是奇数，则只会执行一次加法操作，时间复杂度为 O(1)。

因此，综合考虑，该程序片段的时间复杂度为 O(n/2) 或 O(1)，具体取决于输入 n 的奇偶性。