Как я могу сравнить сложность времени O (n ^ 2) с O (N + log (M))? - PullRequest
Новая
       5

Как я могу сравнить сложность времени O (n ^ 2) с O (N + log (M))?

1 голос
/ 13 апреля 2019

Моя функция 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).

Как я могу сравнить это с временной сложностью GEORADIUS (Redis) с O (N + log (M))? https://redis.io/commands/GEORADIUS

Сложность по времени: O (N + log (M)), где N - количество элементов внутри ограничительной рамки круглой области, ограниченных центром и радиусом, а M - количество элементов внутри индекса.

У моей сложности со временем нет М. Я не знаю, сколько элементов в индексе (М), потому что мне не нужно это знать. Мой индекс часто меняется, почти с каждым запросом и может быть большим.

В какое время сложность лучше?

...