关于Boost RTree实现网格相交查询的时间复杂度正确性确认

第一个代码片段的复杂度判断 #

先看你给出的第一段代码：

for (const auto &[box2, cell2] : RTree_2)
{
    for (const auto &[box1, cell1] :
         RTree1 | bgi::adaptors::queried(bgi::intersects(box2)))
    {
        do_something_with_cells(cell1,cell2);
    }
}

你认为这段代码的时间复杂度是O(NM log(N))，这个判断是错误的。

原因如下：

• Boost RTree的单次相交查询平均复杂度是O(logN + K)，其中K是本次查询返回的相交元素数量（也就是和当前box2相交的box1个数）。
• 整段代码的总复杂度应为O(M*(logN + K_avg))，这里K_avg是单次查询返回的平均相交元素数：
  • 只有极端场景下（比如所有box1都和每个box2相交），K_avg=N，此时复杂度趋近于O(M*(logN + N))≈O(MN)——但主导项是MN，logN的影响可以忽略，也不是你说的O(NM logN)。
  • 正常场景下K_avg远小于N，实际复杂度会远低于O(MN)。

第二个代码片段的复杂度分析 #

再看改写后的代码：

for (const auto &[box2, cell2] : RTree_2)
{
    for (const auto &[box1, cell1] :
         RTree1)
    {
        //check if box1 and box2 intersects using bgi
        bgi::query(box1,bgi::intersects(box2));
    }
}

这段代码的复杂度要看实际操作的意图：

• 如果代码是笔误，实际想直接判断两个矩形是否相交（Boost.Geometry中bgi::intersects(box1, box2)是O(1)的基础几何判断），那总复杂度是O(MN)。
• 如果确实要执行RTree查询操作（这种写法逻辑上没必要，因为已经拿到了box1，直接判断即可），单次查询复杂度是O(logN)，总复杂度才是O(MN logN)。

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