Big-O for While循环

我有这个算法，我试图计算它的复杂性。Big-O for While循环

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）是真，我们从该组直到集合为空除去的元素。我知道该算法运行至少O(n)，但如果if语句为false，它可以运行更多。假设最后一行（更新）需要一个固定的时间。

如何计算这里的复杂度？

来源

2017-08-05 Self

即使你总是选择当时的情况，由于'min（A）'和A操作的收缩，努力超过O（n）。他们通常会拿O（log n）。没有更多的信息，关于其他情况就无从谈起。如果你不走运，并且每当你有一个无限循环时都会被采取。 – Henry

由于'C'的值，它不能是无限循环。在某些时候，当我们到达'C'时，循环将终止。 – Self

除非N_a'为零或负数;-) – Henry

我们首先确定then和else分支在最坏情况下可以运行的频率。在当时的分支中，集合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使用无序数组）使得操作min，remove元素，并分别更新O（n），O（1）和O（1）。总运行时间因此将是O（n * n）。

使用有序数组来表示A，我们分别得到了O（1），O（1）和O（n）的运行时间。最小搜索O（1）操作为每次迭代执行，所以O（n）次。删除elemnt O（1）操作在then分支中，所以执行O（n）次，更新O（n）操作在else分支中，所以执行O（1）次。全部一起给出O（n）的运行时间。但是，如果集合必须在开始时进行排序，我们再次处于O（n log n）。

来源

2017-08-07 04:43:49 Henry

非常明确的分析和解释，但我会回来与你讨论。 – Self

Big-O for While循环

回答

相关问题