如何将时间复杂度 O(n^2) 与 O(N+log(M)) 进行比较?

Question

My Lua 函数：

for y=userPosY+radius,userPosY-radius,-1 do 
for x=userPosX-radius,userPosX+radius,1 do
local oneNeighborFound = redis.call('lrange', userPosZone .. x .. y, '0', '0')
if next(oneNeighborFound) ~= nil then
table.insert(neighborsFoundInPosition, userPosZone .. x .. y)
neighborsFoundInPositionCount = neighborsFoundInPositionCount + 1
end
end   
end

这导致这个公式：(2n+1)^2 正如我正确理解的那样，这将是 O(n^2) 的时间复杂度。

我怎样才能用O(N+log(M))将其与GEORADIUS(Redis)的时间复杂度进行比较？ https://redis.io/commands/GEORADIUS

时间复杂度：O(N+log(M))，其中 N 是由中心和半径分隔的圆形区域的边界框内的元素数，M 是索引内的项数。

我的时间复杂度没有M。我不知道索引(M)中有多少项，因为我不需要知道。我的索引经常更改，几乎每次请求都会更改，并且可能很大。

哪个时间复杂度更好？

Answer 1

假设N和M是自变量，我会像对待O(N3- 7N2- 12N + 42)一样对待O(N + log M)：后者变得O(N3)，仅仅是因为这是对结果影响最大的术语。

尤其如此，因为时间复杂度分析并不是真正考虑运行时的情况。运行时必须考虑N特定限制的较小条款。例如，如果您的算法运行时可以表示为runtime = N2+ 9999999999N，并且N始终在[1, 4]范围内，则更重要的是第二个项，而不是第一个项。

最好将复杂性分析视为N接近无穷大时会发生什么。有了O(N + log M)，想想当你：

• 双N？
• 双M？

第一个影响要大得多，所以我会简单地将复杂性转换为O(N)。

但是，希望您已经注意到我第一段中"独立"一词的使用。我的建议唯一的症结是，如果M实际上是N的某种功能，在这种情况下，它可能成为更重要的术语。

任何扭转log M影响的函数都会这样做，例如相等M = 101010N。