如何化简O(10n)*O(4n²)？乘法项能否舍弃低增长项？

首先明确结论：你的预期是对的，正确化简结果是O(n * n²)（即O(n³)），而化简成O(n²)的做法是错误的。

具体推导步骤 #

1. 大O符号的乘法规则：O(f(n)) * O(g(n)) = O(f(n) * g(n))，因此先将两个表达式内的函数相乘：

   O(10n) * O(4n²) = O(10n * 4n²)
   

2. 计算乘积：10n * 4n² = 40n³，由此得到O(40n³)。
3. 大O符号聚焦于算法的增长趋势，会忽略常数系数（无论系数是40还是其他正数），因此O(40n³)可简化为O(n³)，也就是你所写的O(n * n²)。

关键误区说明 #

“舍弃增长速度较慢的项”是加法场景下的规则（比如O(n) + O(n²)可化简为O(n²)），但这个规则不适用于乘法场景。乘法需要结合两个函数的增长趋势，这里n与n²相乘后的增长速度是n³，远快于n²，不能随意舍弃其中任何一项。

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