基本信息

---

下载

文档摘要

---

第PAGE页共NUMPAGES页

计算机编程中的算法证明题集

一、证明题（每题10分，共3题）

题目1

证明快速排序算法在最坏情况下的时间复杂度为O(n2)。

提示：考虑数组已经完全逆序的情况。

题目2

证明归并排序算法的时间复杂度始终为O(nlogn)。

提示：分析归并排序的递归过程和合并操作的时间复杂度。

题目3

证明二分查找算法在查找成功的情况下，比较次数为?log?n?。

提示：考虑二分查找的递归或迭代过程，分析每次比较后剩余搜索范围的变化。

二、分析题（每题15分，共2题）

题目4

分析以下递归函数的时间复杂度，并给出严格证明。

python

deffactorial