视频封面

 

附上一个视频，如何理解一个算法:

https://www.bilibili.com/video/BV1iZ4y1W7ep

 

选择题

Q1

题目

3-way-MergeSort: 假设不将 MergeSort 的每一步分成两半，而是分成三份，单独进行排序，最后将它们全部合并。 该算法的整体渐近运行时间是多少？ （提示：请注意，合并步骤仍然可以在O(n)时间内实施。）

解答

Step 1: 写下循环

[公式] # 当n是1的时候排序是O(1)

[公式]表示长度为n的数组的运行时间。而MergeSort将数组分成了三份，所以每份数组长度是[公式]，而合并步骤可以在O(n)时间完成，所以整个的运行时间如下:

[公式]

Step 2: 假设 [公式]，令[公式]，因此我们有

[公式] # 在k=0时

[公式] # 把k和n的关系带入step1的公式2

Step 3: 于是我们可以解决这个问题

[公式]

[公式]

[公式]

[公式]

[公式] # 一直这样拆分

[公式]

[公式] # 去掉常数项

[公式] # 把k根据上面的假设换成n

[公式]

Q2

题目

给你函数f和g，使得[公式]。 那么[公式]吗?（这里c是正常数。）你应该假定f和g非递减，并且始终大于1。

解答

根据大O的定义，存在正常数[公式]和[公式]，[公式]时，有

[公式]

让我们得出左侧的边界，我们有

[公式]

为了进一步简化，我们得到[公式]，所以我们有

[公式]

[公式] 带入公式

[公式] # 提取公共项

[公式]

[公式] # 使用g(n)非递减性质

[公式]

所以，存在正常数[公式]和[公式]，当[公式]时，有[公式]

于是[公式]

Q3

题目

再次假设两个（正）非递减函数f和g，使得[公式]。 那么[公式]吗？

解法

不完全是，让我们来检查一些简单的特殊情况。

情况1: f(n)=g(n)=n，这种情况下，2n=O(2n)是正确的。

情况2: f(n)=10n，g(n)=n，这种情况下我们有[公式] # 课程2里面证明过，指数函数的指数和一个常数相乘改变了它的渐进性增长率。

这样，我们可以确定：

该说法并不总是正确的。

该说法并非总是错误的。

那么怎么让这种说法总是正确呢？

根据大O的定义，存在正常数c和[公式]，使得[公式]的时候，有[公式]，就是说[公式]，只需要让[公式]就好了。

Q4

题目

k-way-MergeSort： 假设给定k个排序数组，每个数组包含n个元素，并且你想将它们组合成一个kn个元素的单个数组。 考虑以下方法:

  • 使用讲座中讲解的merge子程序，你可以合并前两个数组
  • 然后将第三个给定数组与前两个数组的合并版本合并
  • 然后将第四个给定数组与前三个数组的合并版本合并，依此类推
  • 直到合并到最后一个（kth）输入数组为止。

将k，n作为输入，那么这个函数的运行时间是多少？

解法

为简单起见，我们说合并所需的时间仅等于列表长度的总和。(因为所有数组已经排好序了，只需要线性遍历它们)

因此对于第一次合并，我们有[公式]

对于第二次合并，我们有[公式]

…

这些数字的总和为

[公式]

Q5

题目

[公式]）。

[公式]

[公式]

[公式]

[公式]

[公式]

解法

一个比较简单的方法是计算一堆值：

很显然答案是这样的:

[公式]

实际上，我们再来看一下，取对数后（取对数不影响它们的渐进性），解决方案非常明显，所有的数取对数后

[公式]

亚线性排序，有 [公式]

多项式排序，有 [公式]

指数增长是最快的 [公式]

所以排列顺序就出来了。

编码题

题目

实现课堂上的逆序对计数。

代码

def count_inversions_and_sort(array1, array2):
    """
    :param array1: 已排序的数组1
    :param array2: 已排序的数组2
    :return: (逆序对个数，排序后的合并数组)
    """
    res = []
    split_inv = 0  # 存放逆序对个数
    i = 0
    j = 0
    l1 = len(array1)
    l2 = len(array2)
    num = l1 + l2  # 总的元素个数

    for _ in range(num):
        if i == l1:  # 数组1遍历完了，只需要把数组2的剩下元素加入数组中就行
            res += [array2[x] for x in range(j, l2)]
            break
        if j == l2:
            res += [array1[x] for x in range(i, l1)]
            break

        if array1[i] < array2[j]:  # 左边的数小
            res.append(array1[i])
            i += 1
        else:
            res.append(array2[j])  # 右边的数小
            j += 1
            split_inv += (l1 - i)  # l1中所有剩余的元素

    return (split_inv, res)


def sort_and_count_inversions(array):
    """
    :param array: 需要排序的数组
    :return: (逆序对个数，排序后的数组)
    """
    if len(array) == 1:
        return (0, array)

    i = len(array) // 2  # 把数组分成左右两个部分
    l_inv, left = sort_and_count_inversions(array[0:i])  # 左逆序对
    r_inv, right = sort_and_count_inversions(array[i:])  # 右逆序对
    split_inv, merged = count_inversions_and_sort(left, right)  # 分离逆序对

    return (l_inv + r_inv + split_inv, merged)

版权声明：本文为siguamatrix原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/siguamatrix/p/12815072.html