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

Question

我简单回顾了计算几何中关于线相交和线排列问题的文献。大多数都是基于平面扫描算法。从计算复杂度的角度来看，在我看来，渐近算法界限是线段数量和术语“k”的函数，其中“k”是边之间相交的数量。例如，最著名的算法之一的时间复杂度为 O(nlogn + "k")，这是输出敏感的。我的问题是很难理解为什么我们不能在提供时间复杂度的同时去掉术语“k”。因为如果我们查看其他算法(例如排序问题)，复杂性并不是完成多少次交换或比较的函数。它只是输入数量的函数。任何见解都会有所帮助。

Answer 1

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