算法的输入是m
和n
。
我的算法的时间复杂度是 O(mn)
。
我有一个时间复杂度为 O((m+n)²)
的基准算法。
我的实现在时间复杂度方面是否优于基准?
最佳答案
如此多的评论者和回答者希望只考虑 m = n
的情况,或者至少当它们以常数因子相关时。这不是它的工作原理。
当我们保持 m
或 n
常量时,您的算法显然更快;例如,如果我们将自己限制在 m = 1
的情况下,那么您的算法的复杂度为 O(n)
而备选方案为 O(n^2 )
,所以在这种受限情况下你的显然更好。
我们可以说 (m+n)^2 = m^2 + n^2 + 2mn
显然是 Ω(mn)
其中 Ω
表示这是一个下限,您的算法(渐近地)总是至少一样好;即没有其他算法渐进地优于您的算法的限制情况。但我们确实知道在有限的情况下你的更好。所以,总的来说,你的更好。
关于algorithm - O(mn) 比 O((m+n)^2) 好吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68543485/