我正在学习《算法导论》中与计算几何相关的章节。在第33.1-4题的练习中，要求我们“展示如何在O(n*n*lg n)的时间复杂度内确定一个n个点的集合中是否有任意三个点是共线的?”。通过取出每次的三个点并进行叉积运算，可以轻松地在O(n*n*n)的时间复杂度内完成此任务，但我不知道如何在O(n*n*lg n)的时间复杂度内做到这一点。请求帮助。
CLRS：33.1-4：展示如何在O（n * n * lg n）时间内确定n个点集中任意三个点是否共线？
4
- kafee651
1个回答
4
对于任意两个点P和Q，令slope(P,Q)表示通过P和Q的直线的斜率。现在，三个点P、Q和R共线当且仅当slope(P,Q) = slope(P,R)。因此，固定一个点P，你可以在O(n*log n)时间内确定是否存在另外两个点Q和R，使得PQR在同一条直线上。这可以通过计算集合中所有其他点Q的slope(P,Q)并检查是否有重复来轻松完成 - 使用类似集合的结构或者只是排序并检查是否有重复。现在，遍历所有选择的P，总运行时间为O(n*n*log n)。
- Pradhan
2
@n.m. 我错过了什么？ - Pradhan
可以使用基于哈希的数据结构，在高概率下以O(n^2)的时间复杂度完成。 - Niklas B.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 3 大O符号计算，O(n) * O(log n) = O(n log n)。
- 5 解决递归：T(n) = T(n^(1/2)) + Θ(lg lg n)
- 48 面试问题：三个数组和O(N*N)。
- 5 O(n) + O(n log n) 是否等于 O(n log n)？
- 9 O(n) + O(n) = O(n)?
- 3 为什么 lg(n!) = O(nlg(n))？可能的解释。
- 5 在O(n log n)时间内找到特殊点k的算法
- 9 在给定 n 个点 (x,y) 的情况下，是否可以在 O(n logn) 时间内找到负斜率对数？
- 6 如何在O(n*log(n))时间内找到并打印n个给定圆的交点？
- 7 证明 n! = O(n^n)