java - Big O Notation，添加不同意义的循环

Question

我保证这是最后一个 Big 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)。添加这些时，删除第一项是否正确？并说整个 Big O 是 O(n^2)？

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

Answer 1

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