1

我保证这是最后一个大 O 问题

以下循环的大 O 表示法...

     for (int i = n; i > 0; i = i / 2){
        for (int j = 0; j < n; j++){
           count++;
        }
     }
     for (int k = 0; k < n; k++){
        for (int m = 0; m < n; m++){
           count++;
        }
     }

这就是我认为我确定的。

第一组嵌套循环有O(n*log2(n)) ，第二组嵌套循环是O(n^2). 添加这些时删除第一个术语是否正确？并说整体大 O 是O(n^2)？

第二个问题，当为系列循环添加大 O 符号时，删除不太重要的项总是正确的？

4

2 回答 2

4

你的两个问题的答案都是肯定的。您总是会丢弃较小的项，因为它们被较大的项所支配，并且在进行大 O 分析时n您只关心大。n

于 2013-01-25T03:18:28.100 回答
1

原因是渐近地n*log2(n)被支配 n^2：对于足够大n的 ，|n * log2(n)| < |n^2|。

如果您不明白为什么这意味着您可以删除该n*log2(n)术语，请尝试n^2在两侧添加：

n^2 + n*log2(n) < n^2 + n^2
n^2 + n*log2(n) < 2 * n^2

因此，如果我们知道我们可以忽略一个常数因子k，我们就知道我们可以忽略一个不太重要的项。

于 2013-01-25T03:21:18.713 回答