数据结构第一章作业

第一题

设 $n$ 是偶数，试计算运行下列程序段后 $m$ 的值，并给出该程序段的时间复杂度。

m = 0;
for (i = 1; i <= n; i++)
    for (j = 2 * i; j <= n; j++)
        m = m + 1;

m=m+1 这行语句总共执行次数为： $$ \sum_{i=1}^n{max{n-2\times i + 1,0}} = \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor}{n-2\times i + 1}=(n+1)\cdot \lfloor \frac{n}{2}\rfloor - \lfloor \frac{n}{2}\rfloor \cdot (1 + \lfloor \frac{n}{2}\rfloor) $$ 由 $n = \lfloor \frac{n}{2}\rfloor + \lceil \frac{n}{2}\rceil$，上式进一步化为： $$ \lfloor \frac{n}{2}\rfloor \cdot (n - \lfloor \frac{n}{2}\rfloor) = \lfloor \frac{n}{2}\rfloor \cdot \lceil \frac{n}{2}\rceil = O(n^2) $$ 所以，该程序段的时间复杂度 $T(n) = O(n^2)$。

第二题

下列算法对一 $n$ 位二进制数加 $1$，假如无溢出，该算法在最坏情况下时间复杂度是什么？并分析它的平均时间复杂度。

void func(int A[n]) // A[n]中每个元素取值0或1，假设下标从1->n
{
    int i = n;
    while (A[i] == 1)
    {
        A[i] = 0;
        i--;
    }
    A[i] = 1;
}

最坏情况下，每一位都是 $1$，时间复杂度 $T(n) = O(n)$。
平均情况下，假设所有 $n$ 位二进制数等概率出现，$T(n) = \frac{n + 1 + \sum_{i=1}^{n}2^{n-i}\cdot i}{2^n} = \frac{2^{n+1}-1}{2^n} = O(1)$。

第三题

调用下列函数f(n)回答下列问题：

试给出f(n)值的大小，并写出f(n)值的推导过程；
假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。

int f(int n)
{
    int i, j, k, sum = 0;
    for(i = 1; i < n + 1; i++)
    {
        for(j = n; j > i - 1; j--)
            for(k = 1; k < j + 1; k++)
                sum++;
        printf("sum=%d\n", sum);
    }
    return (sum);
}

由于 $j > i - 1 \ge 0$，最内层对 $k$ 的循环总是执行 $j$ 次，等价于 sum += j。

所以对于固定的 $i$，sum累计增加： $$ \sum_{j = i}^{n}{j} = \frac{(i + n)\cdot (n - i + 1)}{2} $$ 故 f(n) 的值为： $$ \begin{aligned} f(n) &= \sum_{i = 1}^{n} \frac{(i + n) \cdot (n - i + 1)}{2} \ &= \frac{1}{2} \sum_{i=1}^{n} \left( n^2 + n - i \cdot (i - 1) \right) \ &= \frac{1}{2} \left( n^3 + n^2 - \frac{(n + 1) \cdot n \cdot (n - 1)}{3} \right) \ &= \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n \end{aligned} $$ f(5) 的大小为 55，执行 f(5) 时输出如下：

sum=15
sum=29
sum=41
sum=50
sum=55