1 
for(int i=N; i>0; i=i/2)  
    irrelevant statement;

我被要求找到复杂度类，但我不确定我应该使用 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) 然后在我放弃 N 之后是 O(N^2)？

4

3 回答 3

3

对于第一个，如果将 N 加倍，还要执行多少操作？

于 2010-10-17T13:08:17.723 回答
2

第一个具有复杂度等级 O(log2(n))，因为当你将 n 加倍时，它只会增加一个操作。

第二个是 O((n^2)/2)，或者只是 O(n^2)。理解这一点的最简单方法是将其想象成一个形状。你有两个 for 循环，所以你知道最终的复杂度是 n^2，但是随着第一个循环的继续，第二个循环减少到零。这有效地创建了一个三角形。

于 2010-10-17T13:15:33.333 回答
1

你说的第二个是对的。第一个是 O(logN)，第二个是 O(N^2)。但是有一个但是。您所说的irrelevant statement可能非常相关。如果该语句是，例如一个函数调用，它又在 O(N) 中工作，那么复杂度将分别变为 O(N*logN) 和 O(N^3)。所以，如果irrelevant statement是 O(1)，你是对的。

于 2010-10-17T13:14:59.720 回答