Big-O符号代码算法分析作业
Big-O符号代码算法分析作业
提问于 2010-10-17 21:05:17
for(int i=N; i>0; i=i/2)
irrelevant statement;我被要求找到complexity类，我不确定我应该使用Big-Omega表示法还是Big-O表示法？但我假设它是O(N/2)，然后是O(N)，如果我去掉常量。
for (int i=0; i<N; i++)
for (int j = i+1; j<N; j++)
irrelevant statement;对于这个，我相信它是O(N) * O(N+1) -> O(N^2 + N)，然后是O(N^2)，在我去掉N？
回答 3
Stack Overflow用户
发布于 2010-10-17 21:08:18
对于第一个，如果将N加倍，将会执行多少个操作？
Stack Overflow用户
发布于 2010-10-17 21:15:33
第一个的复杂度等级为O(log2(n))，因为当你将n加倍时，它只增加了一个操作。
第二个是O((n^2)/2)，或者就是O(n^2)。理解这一点最简单的方法是把它想象成一个形状。您有两个for循环，所以您知道最终的复杂度是n^2，但是随着第一个循环的继续，第二个循环的复杂度就会减少到零。这有效地创建了一个三角形。
Stack Overflow用户
发布于 2010-10-17 21:15:00
你对第二个问题的看法是对的。第一个是O(logN)，第二个是O(N^2)。但是有一个是但是。你所说的irrelevant statement可能是非常相关的。例如，如果语句是以O(N)方式工作函数调用，则复杂度将分别变为O(N*logN)和O(N^3)。所以，如果irrelevant statement是O(1)，那么你是对的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3953318
复制相关文章
相似问题
腾讯云开发者
