多变量Big O复杂度分析：分式化简与常数阶判定疑问

问题1：双变量复杂度O(n/k + n + k)的简化 #

可以简化为O(n + k)，原因如下：

• 大O符号的本质是描述输入规模趋近无穷时的渐近上界，只保留增长最快的主导项
• 当k趋近于无穷大时，n/k趋近于0，完全被k项覆盖，没有保留的必要
• 当n趋近于无穷大时，n/k的增长速率是线性的，但系数是1/k（k是独立变量），它的增长速度永远慢于n，因此n才是这个场景下的主导项，n/k可忽略
• 无论n和k如何变化，n/k都不会成为主导项，所以可以安全移除，得到更紧的上界O(n + k)

问题2：单变量复杂度O(1/n)的简化 #

可以简化为O(1)，原因很直接：

• 大O符号关注的是输入规模n趋近无穷时的运行时间趋势，当n→∞时，1/n趋近于0，此时时间复杂度被常数项主导
• O(1)代表常数时间复杂度，也就是运行时间不随输入规模增长而变化，1/n的渐近上界就是常数级，因此可以简化为O(1)

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