数据结构习题解析：时间复杂度与算法优化

"南邮数据结构作业答案讲解.pptx" 在数据结构的学习中，时间复杂度是一个重要的概念，它衡量了算法执行效率。这里，我们通过几个具体的例子来理解和分析时间复杂度。 首先，来看第一个程序段： ```markdown (1)i=1;k=0; do{ k=k+10*i;i++; }while(i<=n-1) ``` 这个程序段中，划线语句`k=k+10*i`在循环内部，会随着`i`的递增执行`n-1`次，因此它的执行次数是`n-1`。由于每次迭代中的操作数量是常量，所以其渐近时间复杂度是`O(n)`。 第二个程序段： ```markdown (2)i=1;x=0; do{ x++;i=2*i; }while(i<n); ``` 在这个例子中，`x++`的执行次数是对数级的，因为`i`每次翻倍直到超过`n`，所以执行次数大约是`log2n`，其渐近时间复杂度是`O(log2n)`。 第三个程序段涉及嵌套循环： ```markdown (3)for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) for(int k=1; k<=j; k++) x++; ``` 三层循环中，最内层的`x++`执行的次数可以表示为一个三重积分的近似值，即`n(n+1)(n+2)/6`，这在大O记法中表示为`O(n^3)`，因为随着`n`的增长，最高阶项`n^3`占主导地位。 第四个程序段： ```markdown (4)x=n;y=0; while(x>=(y+1)*(y+1)) y++; ``` 这个循环中，`y++`的执行次数与`y`满足的平方根关系，大致等于`n^(1/2)`，因此渐近时间复杂度是`O(n^(1/2))`。 接下来，我们看看数组操作的实例。第二章习题讲解中，介绍了如何用逆序排列一维数组： ```markdown void Invert(T elements[], int length) { Te; for(int i=1; i<length/2; i++) { e=elements[i-1]; elements[i-1]=elements[length-i]; elements[length-i]=e; } } ``` 这个算法的时间复杂度是`O(n/2)`，但由于常数因子不计入时间复杂度，所以实际的渐近时间复杂度是`O(n)`。 最后，是关于链表操作的算法，将单链表逆序排列： ```markdown Node* pInvert(Node* first) { Node* p=first, *q; first=NULL; while(p) { q=p->Link; p->Link=first; first=p; p=q; } return first; } ``` 这个算法遍历链表一次，时间复杂度为`O(n)`，其中`n`是链表中的节点数。 这些题目覆盖了时间复杂度分析的基本方法，包括常量时间、线性时间、对数时间以及立方时间的复杂度。对于数组和链表的操作，也展示了常见的排序和反转算法，这些都是数据结构课程中的核心知识点。