0

我试图帮助一位朋友分析他的算法的复杂性，但我对 Big-O 表示法的理解非常有限。

代码如下：

int SAMPLES = 2000;
int K_SAMPLES = 5000;

int i = 0; // initial index position    
while (i < SAMPLES)
{
    enumerate();                       // Complexity: O(SAMPLES)
    int neighbors = find_neighbors(i); // Complexity: O(1) 

    // Worst case scenario, neighbors is the same number of SAMPLES
    int f = 0;
    while (f < neighbors) // This loop is probably O(SAMPLES) as well.
    {
        int k = 0; // counter variable
        while (k < K_SAMPLES) // Not sure how to express the complexity of this loop.
        {                     // Worst case scenario K_SAMPLES might be bigger than SAMPLES. 

            // do something!

            k++;
        }
        f++;
    }

    i++;
}

代码中有 2 个函数，但我能够识别它们的复杂性，因为它们很简单。然而，我无法表达内部while循环的复杂性，但即使在测量之后，我仍然需要帮助将所有这些复杂性组装成一个表示算法计算复杂度的公式。

在这件事上我非常需要帮助。谢谢！

4

2 回答 2

3

从最内层循环到最外层的最坏情况分析（轻度滥用“=”符号）：

->  O(K_SAMPLES)                    -- complexity of just the k-loop

->  neighbors * O(K_SAMPLES)         -- complexity of f-loop accounted for
 =  SAMPLES * O(K_SAMPLES)          -- since neighbors = SAMPLES in worst case
 =  O(SAMPLES * K_SAMPLES)

->  O(SAMPLES) + O(SAMPLES * K_SAMPLES)  -- adding complexity of enumerate()
 =  O(SAMPLES + SAMPLES * K_SAMPLES)
 =  O(SAMPLES * K_SAMPLES)

由于渐近增长更快，该SAMPLES术语被删除。SAMPLES * K_SAMPLES更正式地说，

When C >= 2, SAMPLES >= 1, K_SAMPLES >= 1 then

SAMPLES + SAMPLES * K_SAMPLES  <=  C(SAMPLES * K_SAMPLES)
SAMPLES * (K_SAMPLES + 1)  <=  SAMPLES * C * K_SAMPLES
K_SAMPLES + 1  <=  C * K_SAMPLES

有关具有多个变量的 big-O 的更多信息，请参见此处。继续我们的最后一个循环：

->  SAMPLES * O(SAMPLES * K_SAMPLES)    -- complexity of i-loop accounted for
 =  O(SAMPLES^2 * K_SAMPLES)

请注意，根据 返回的平均数find_neighbors(i)，它可以使平均 big-O 不同。

于 2013-03-06T06:39:11.897 回答
0

O（邻居* K_SAMPLES）

如果邻居 << K 那么这在 K_SAMPLES 中更接近线性

如果邻居按 K_SAMPLES 顺序排列，则在 K_SAMPLES 中是二次的

于 2013-03-05T20:52:10.673 回答