算法分析(big-O)
算法分析(big-O)
提问于 2013-03-06 04:47:36
我试图帮助一个朋友分析他的算法的复杂性，但我对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++;
}代码中有两个函数，但我能够识别出它们的复杂性，因为它们很简单。然而，我无法表达内部while循环的复杂性，但即使在测量之后，我仍然需要帮助将所有这些复杂性组装成一个表示算法计算复杂性的公式。
在这件事上我真的需要帮助。谢谢!
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-03-06 14:39:12
从最内循环到最外循环的最坏情况分析(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 * K_SAMPLES的渐近增长速度更快，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)返回的平均值，它可以使平均大O值有所不同。
Stack Overflow用户
发布于 2013-03-06 04:52:11
O(邻居* K_SAMPLES)
如果与<< K相邻，则在K_SAMPLES中这更接近线性
如果邻域按K_SAMPLES顺序排列，则这在K_SAMPLES中是二次的
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15233803
复制相关文章
相似问题
腾讯云开发者
