算法的算法分析(big-O)

Question

我正试图帮助一位 friend 分析他的算法的复杂性，但我对大 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 循环的复杂性，但即使在测量之后，我仍然需要帮助将所有这些复杂性组装成一个表示算法计算复杂性的公式。

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

Answer 1

从最内层循环到最外层循环的最坏情况分析 (with mild abuse of the "=" sign):

->  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

有关具有多个变量的大 O 的更多信息，请参阅 here .继续我们的最后一个循环:

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

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