吴紫航

不在故不思

0%

【习题解答】 蛮力算法设计

发表于 更新于 分类于 阅读次数： 评论数：

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ##3.2 ###(1) 大概说一下证明思路，用类似于数学归纳法的写法(基本情况+归纳推理)来证明循环不变量即可。

  1. 对于内循环，循环不变量是：

在循环结束时，始终比中的元素大；

  1. 对于外循环，循环不变量是：

在循环结束时，部分按从小到大排好序了。

注意，本题解已经是一个清晰的思路，具体写法细节不再赘述。

###(2) 题干说明了以比较操作为关键操作，那么最坏情况时间复杂度和平均时间复杂度是一样的。

都是

###(3) 这个改进非常精巧，最后一次交换的位置如果为p，意味着p右侧的元素都已经排好序了(否则最后一次交换会发生在p的右边，从而矛盾)，且p左侧的元素一定都不比p位置的大(否则左侧该元素在当初的内循环中就会被冒泡到p右侧才对，矛盾)。

由于没告诉输入的概率分布，但是容易验证对于很多输入，时间复杂度都有改进，所以可以认为平均时间复杂度是有影响的；但如果假设数组中一个数比另一个数大的概率都是0.5，那么平均复杂度还是，从这个角度似乎也可以回答平均时间复杂度没有影响，但需给出合理解释；对于全逆序输入，最后一次交换始终发生在内循环的最后一次，因此最坏时间复杂度不会减小，还是

##3.5 ### 算法设计

正确性证明和复杂度分析

外循环是从开始，但我们可以把当作是一个非常大的数，以保证输出的合法性。

先如下证明两个循环不变量：

(i)每次外循环结束都得到

其中满足且;

(ii)每次内循环进行条件判断时，中没有元素大于等于且没有元素大于

我们发现这两个不变量的证明相互有联系，单独的用证明其中一个比较困难，因此考虑用强数学归纳法的思路来做：

(1)基本情况：

第一次外循环，显然找到了，循环不变量满足;

每次外循环的第一次内循环也满足循环不变量，因为和之间没有元素。

(2)归纳推理：

  • 假设前次外循环都满足循环不变量，即都已经赋值正确的结果。
  • 假设第次外循环的前次内循环都满足循环不变量

那么对于第次外循环的第次内循环，反设其不满足内循环的不变量，即存在一个，使得或，如果有多个满足的，我们取最靠近的。

  • 若 且，则矛盾在于第i次外循环的内循环的第一次条件判断就不生效，仍然不会被访问到
  • 若 且，则矛盾在于中没有比大的元素，则，不会被访问到
  • 若 且，则,则一定比先被跳转到，矛盾在于，则不会被访问到
  • 若 且，则，故一定比先在内循环访问到，则，则不会被访问到

因此第次外循环的第次内循环必然满足循环不变量。而最后一次内循环条件判断不生效后，也就找到了左边比其大且最靠近的元素的下标。这样第次外循环结束时，外循环不变量也得到了满足。

两个循环不变量的证明就完成了，但题目还没解答完成。

因为外循环最后一次的不变量满足，所以获得正确结果，算法正确。

把是用于跳转下标的，如果第i次外循环在位置对应的内循环中发生了跳转，则说明，由已经证明的内循环不变量，中元素都比小，因此在第次外循环中都不可能使用跳转;而第w次外循环()也不可能使用跳转，否则找到，使得，不满足内循环的不变量。因此在整个程序运行过程中，跳转数组的每个元素最多被使用1次，内循环是线性代价，而外循环也是线性的，故算法复杂度是

##3.6 本题算法较直观，只给出大概思路，而不是算法格式的答案。此外注意，一般空间开销都是指除了保存输入数据以为额外引入的空间开销。 ###(1) 时间复杂度，空间复杂度的算法

用冒泡排序的思想，外循环是对于1到k的部分，内循环是将其移动到数组的倒数对应位置。

###(2) 时间复杂度，空间复杂度的算法

引入额外空间开销，保存数组的两个分解子数组，然后合并即可

###(3) 时间复杂度，空间复杂度的算法

对于一个数组，将其整体翻转的复杂度是线性的：只需要一次循环，从两侧往中间遍历，两边交换位置，重合时结束循环。

那么符合题目要求的算法可以是：对于数组的左右两个子数组，分布进行一次翻转，然后再对整个大数组作一个翻转。这样三次翻转，复杂度是，并且引入O(1)的额外空间即可(每次交换元素位置的时候使用)。

##3.7 答：本题思路和3.6的第(3)问解法一样，即子串分别翻转、总串再整体翻转一次，时间复杂度,空间复杂度。

##3.8 (1) + 0个名人的情况，比如大家谁都不关注的情况，因为名人是需要被其他人关注的。 + 1个名人的情况，比如大家都关注甲，甲不关注任何其他人 + 超过1个名人的情况，比如名人有甲和乙，因为甲是名人，故甲不关注乙；因为乙是名人，所以甲关注乙，矛盾。

所以要么0个名人，要么有1个名人。

  1. 简单的思路就是两层遍历，第i层外循环的任务是判断第i个是不是名人，而内循环就是问其他人有没有关注第i个人。

而改进的思路是这样的，随便抽两个人A和B，问A是否关注了B。 + A关注了B，则A不是名人，删除A + A没关注B，则B不是名人，删除B

一直删到只剩下一个人的时候，该人就是候选名人，一次循环判断该唯一的候选名人是不是名人即可，复杂度。

##3.9 只给思路，具体算法细节略去 ###(1) 两层外循环确定子序列首尾的下标，最内循环计算加和，然后三层循环找到最大的子序列和即可。

复杂度

###(2) 前一问给出的算法的最内层循环是很多余的，可以在第二层循环，即移动子序列尾部下标的同时，以O(1)的时间代价更新子序列的和。

复杂度

###(3) 每次把数组分成左右两半，最大连续子序列只可能出现在以下的情况： (i) 左半边和右半边的单侧，这种情况递归求解即可 (ii) 跨越左右两侧，这种情况用线性时间代价求得“以左边最后一个元素结尾的最大连续子序列”、“以右边第一个元素开始的最大连续子序列”，然后相加即可

然后在上述的情况中选最大的连续子序列即可。

时间复杂度由master定理：，复杂度是

###(4) 一次遍历即可，第i次循环，求得以第i个元素结尾的最大连续子序列的和。

基本情况：第1次循环显然O(1)获得以第1个元素结尾的最大连续子序列的和是。

归纳推理：加入已经知道了以第i-1个元素结尾的最大连续子序列的和是

  • 若tmp大于0，则以第i个元素结尾的最大连续子序列的和是
  • 若tmp小于等于0，则以第i个元素结尾的最大连续子序列的和是

我们发现循环体内的时间开销是常数级O(1)，所以整个算法是线性的时间复杂度。

###(5) 动态规划直观的思想就是保存中间有用的结果，并通过调整计算的顺序，来消除冗余的步骤。

先考虑子问题：求解以第i个元素结尾的最大子序列的和，i从1到n。

求这些子问题得到的中间结果是值得保存的，假设保存在数组中

状态转移方程是

这样每次状态转移都是的代价，MaxSum填满需要代价，那么在MaxSum中遍历一遍找到最大值即是最大连续子序列的和。

用动态规划时间复杂度是。

注：其实(4)的方法本质就是动态规划的思想：保存中间的有用结果，以及讲究计算的顺序；同时由(4)的思路可以把(5)的方法在空间复杂度上改进到O(1)