graphics - 线段或边缘交叉点查找算法的时间复杂度

Question

我简要回顾了计算几何中关于线交叉和线排列问题的文献。其中大部分基于平面扫描算法。从计算复杂度的角度来看，在我看来，渐近算法边界是线段数和术语“k”的函数，其中“k”是边之间的交叉点数。例如，最著名的算法之一具有 O(nlogn + "k") 的时间复杂度，这是输出敏感的。我的问题是难以理解为什么我们不能在提供时间复杂度的同时摆脱术语“k”。因为如果我们看一下其他算法，例如排序问题，复杂性不是完成多少交换或比较的函数。它只是输入数量的函数。

Answer 1

如果您想严格按照输入中的线段数来表达最坏情况的复杂性，那么您必须假设 K 可能有最大的交叉点数（即 N ²）。因此，如果您愿意，也可以将具有 O(N log N + K) 时间复杂度的算法（例如 Balaban's）称为 O(N ² + N log N) 或 O(N * (N + log N))。