时间戳

首页 > 解决方案 > 为什么算法复杂度为 O(N*log(N+M))？

algorithm - 为什么算法复杂度为 O(N*log(N+M))？

问题描述

考虑以下代码（Github 链接）

变量min最多是，M变量max最多是M*N 我们对区间进行二分搜索[min, max]。我们调用的每次迭代divisionSolvable都是O(N)恕我直言，整体复杂性时间是O(N*log(NM)).

你能解释一下为什么不是这样吗？

标签： algorithmtime-complexitycomputer-sciencecomplexity-theory

解决方案

不看链接，注意O(log(NM)) = O(log(N+M)). 事实上，对于N>=2和M>=2，我们有：

log (N+M) < log(NM) = log(N) + log(M) < log(N+M) + log(N+M) = 2 log(N+M).

O()用which 删除常量的定义来完成它。

推荐阅读