Big-O表示法疑问：O(n)+O(log₂n)=O(n)是否成立？我的结论正确吗？

待分析代码 #

for(int i = 1; i < n; i++){
    for(int j = 1; j < 100; j++){
        System.out.println("Hello World");
    }
}

int k = 1;
while(k < n){
    k = k * 2;
}

用户分析内容 #

外层for循环执行n次，复杂度为O(n)；内层for循环固定执行100次，为O(1)，故两层for循环整体为O(n)。while循环中k每次翻倍，执行次数为log₂n，复杂度为O(log₂n)。
查阅资料得知O(nlogn)仅出现在对数复杂度操作嵌套在线性循环内的情况，此处while循环独立于for循环，因此推测O(n)+O(log₂n)=O(n)而非O(nlogn)。

解答 #

你的分析结论完全正确，这段代码的整体时间复杂度就是O(n)。

为什么包含O(log₂n)整体仍为O(n)？ #

Big-O表示法的核心是描述算法在n趋近于无穷大时的增长趋势，只保留增长速度最快的主导项，忽略增长更慢的项和常数：

• 当n足够大时，n的数值会远远超过log₂n（比如n=100万时，log₂n≈20，n是它的5万倍）
• 两个顺序执行的操作，总复杂度是各自复杂度的和。在O(n) + O(log₂n)中，O(n)的增长速度远快于O(log₂n)，所以O(log₂n)项对整体增长趋势的影响可以忽略不计，最终整体复杂度取主导项O(n)。

另外你关于O(nlogn)场景的判断也准确：只有当对数复杂度的操作嵌套在线性循环内部时，才会产生O(nlogn)的复杂度（比如外层循环n次，每次都执行一个O(logn)的操作，总复杂度就是n*logn），而这里两个循环是独立顺序执行，所以是加法而非乘法。

内容的提问来源于stack exchange，提问作者Petetunze