algorithm - 你如何计算这个算法的空间复杂度？

Question

我正在研究算法的空间复杂度。有一种算法可以计算数组中每一对的最大值，直到列表长度变为 1。给定数组是 [25,22,27,33]。

[25] [22] [27] [33] 
  [25] [27] [33]
    [27] [33]
       [33]

你如何计算这个算法的空间复杂度？

标签： algorithmcomputer-science

Answer 1

如果你能提供一个代码就可以了，我们可以计算时间和空间复杂度。

首先，你是丢弃数组的最低元素还是一些随机元素？如果您在每次迭代中删除最低元素，这是一个简单的问题。在 O(n) 时间复杂度中，您可以找到总和最高的一对元素。实际上，您找到两个具有最大值的数字，并将它们存储为所有迭代中的最高对，然后在所有迭代中减少元素的数量，并且需要 O(n) 时间来重新排列数组，并且您需要这样做 n -1 次。上限为 O(n^2)。否则，如果你丢弃随机数，算法的结构是相同的，但你需要在当前数组中找到两个最大数。