algorithm - Big-O for While 循环

Question

我有这个算法，我正在尝试计算它的复杂度。

A = {a_1, a_2, a_3, ...}
w = 0
while A != empty
   a' = argmin(A)  #a' is the element with smallest y_a
   if (N_a' + w > C)
      A = A - {a'}
   else
      x_a' = x_a' + 1
      w = w + N_a'
      Update the y_a' value in A using x_a'

A 是一个集合，如果条件 (N_a' + w > C) 为 true，我们从集合中删除一个元素设置直到集合为空。我知道该算法至少运行 O(n)，但如果 if 语句为 false，它可以运行更多。假设最后一行(更新)花费恒定时间。

如何计算这里的复杂度？

Answer 1

让我们首先确定 then 和 else 分支在最坏情况下可以运行的频率。在 then 分支中，集合 A 变小一个元素，因此它只能执行 n 次(其中 n 是 A 中元素的初始数量)。 else分支最多可以执行C次(取N_a'=1，必须>=1)。 C 是一个常数，所以这是 O(1)。因此，总迭代次数为 O(n)。

关键点现在是用于A的数据结构。必须支持三个操作:找到最小值、删除最小元素和最后一行的更新。当我们选择最小堆时，这些操作中的每一个都可以在 O(log n) 中完成。请注意，在这种情况下，更新不是 O(1) 时间。总运行时间现在是 O(n log n)。

朴素的最小搜索(即对 A 使用一个 uordered 数组)使操作最小化、删除元素和更新操作分别为 O(n)、O(1) 和 O(1)。因此，总运行时间为 O(n*n)。

使用有序数组表示 A，我们的三个操作的运行时间分别为 O(1)、O(1) 和 O(n)。每次迭代都会执行最小搜索 O(1) 操作，因此 O(n) 次。 remove elemnt O(1) 操作在 then 分支，所以执行了 O(n) 次，update O(n) 操作在 else 分支，所以执行了 O(1) 次。将所有这些放在一起给出了 O(n) 的运行时间。但是，如果必须在开始时对集合进行排序，我们的时间又是 O(n log n)。