python - 最大磁盘空间的时间和空间复杂度

Question

from collections import deque
def findMax(hardDiskSpace, k):
    n = len(hardDiskSpace)
    if n * k == 0:
        return []
    if k > n:
        return []

    deq = deque()
    res = []
    i = 0
    while i < n:
        if deq and deq[0] == i - k:
            deq.popleft()
        while deq and hardDiskSpace[deq[-1]] > hardDiskSpace[i]:
            deq.pop()
        deq.append(i)

        if i >= k - 1:
            res.append(hardDiskSpace[deq[0]])
        i += 1
    print(res)
    print(max(res))


if __name__ == '__main__':
    hdd = [62, 64, 77, 75, 71, 60, 79, 75]
    k = 4
    findMax(hdd, k)

一家公司在其办公室之一的计算机上进行分析。计算机沿单行间隔开。分析按以下方式进行:选择一定数量的计算机的连续段，从行的开头开始。分析每台计算机上的可用硬盘空间。确定该段内的最小可用磁盘空间。在对第一个段执行这些步骤后，然后对下一个段重复，继续此过程直到行的末尾(即，如果段大小为 4，将分析计算机 1 到 4，然后是 2 到 5，依此类推.)给定此分析过程，编写一个算法以在分析过程中找到的所有最小值中找到最大可用磁盘空间。
输入
输入由三个参数组成:
numComputer:表示计算机数量的整数
hardDiskSpace:表示计算机硬盘空间的整数列表
segmentLength:一个整数，表示每次迭代中要考虑的连续计算机段的长度

输出
返回一个整数，表示分析期间找到的所有最小值中的最大可用磁盘空间。
例子
输入:
计算机数量 = 3
硬盘空间 = [62, 64, 77, 75, 71, 60, 79, 75]
段长 = 4
输出:64

谁能解释一下上述问题的时间和空间复杂度。

Answer 1

列出的解决方案在时间和空间上都是线性的 (O(N))。它也不能比这更好，因为您至少需要阅读输入。

我将从空间复杂度开始，因为它更容易。

• 给你一个大小为 N 的列表输入。
• 您将使用的唯一额外内存是保存当前最小值及其可能的后继者的双端队列。 if deq and deq[0] == i - k: deq.popleft()部分保证此队列永远不会大于 segmentLength .
• 除了几个一次性变量外，没有使用额外的空间。

因此空间复杂度为O(N)。

时间复杂度也是O(N)。让我们看看原因:

• 外围while i < n:在整个计算机列表上迭代一次。索引i每一步都会增加，所以我们不会再逗留了。那么外圈的内部呢？
• 也没有错:我们经过的每个元素(高清空间)都被附加到队列中。
• 我们经过的每个元素都会在某个时刻从队列中移除(除了那些比段大小更接近数组末尾的元素。这不会以任何方式改变结果)。因此，对于每一个元素，我们都执行一次 push 和一次 pop 或一次 popleft。 pop、push 和 popleft 都是在恒定时间内完成的 - 由 deque 集合提供，所以我们仍然是线性的。
• 唯一可能可疑的部分是内部 while deq and hardDiskSpace[deq[-1]] > hardDiskSpace[i]: .但是，由于它只执行 pop当队列非空并且我们从不多次插入任何元素时，这很好。

我们应该开始的部分可能是正确性。但是，由于您没有询问，所以我最后离开:

正确性的关键是我们用来寻找最小值的双端队列结构。最终的 max(result) 只是画龙点睛的一笔，因为只需遍历结果数组即可在线性时间内找到最大值。

在每次迭代中，我们:

• 检查双端队列中最左边的索引是否已过时。 (不再是当前片段的一部分)
• 检查最右边的索引元素是否小于当前索引的元素。如果是，我们将其删除。重复直到它不再为真或双端队列为空。这保证了最左边的元素保持最小 - 如果不是，我们会在这一步中将其删除。
• 我们将新添加的内容插入队列。 (所以队列持有一个非升序的最小候选者序列)
• 如果我们已经加载了至少一个完整的片段，我们将最左边的索引元素添加到结果集中。

不确定这是否可以作为证明，但我有足够的理由确定它有效。有趣的事实 - 我不得不重写这部分，因为我采用了一种略有不同的方法，并且在进行解释的过程中发现情况并非如此，我感到很困惑。