运行时说明
有人可以向我解释为什么这个算法的递归部分的运行时间为
T(n) = {O(1), if n ≤ 3; {Tf(n/2)+Tc(n/2)+O(n)，如果n＞1 3
.->其中Tf(n/2)代表T(n/2)的下取函数，Tc(n/2)代表上取函数？？？
该算法称为 Shamos，主要步骤是：
- 如果 n ≤ 3，则通过暴力找到最近的点并停止。
- 找到一条垂直线 V，将输入集分为两个大小不相交的子集 PL 和 PR 尽可能平等。指向左侧或线上 属于 PL，右边或线上的点属于 PR。没有一点属于两者，因为 这些集合是不相交的。
- 递归地找到 PL 中最近一对点的距离 δL 和最近一对点的距离 δR 公关配对。
令 δ = min(δL, δR)。输入集合 P 中一对最近点的距离是 在递归步骤中找到的点（即 δ）或由 PL 中点之间的距离组成 并在公关中获得一分。
(a) PL 中的唯一候选点和 PR 中的唯一候选点必须位于由 线 V 左侧距离 δ 处的线和 V 右侧距离 δ 处的线
(b) 令 YV 为按非递减 y 坐标排序的条带内点的数组 （即，如果 i ≤ j，则 YV [i] ≤ YV [j]）。
(c) 从 YV 中的第一个点开始，逐步遍历除最后一个点之外的所有点，检查距离 将此点与接下来的 7 个点（如果少于 7 个点，则为剩余的任何点）。如果一个 找到距离严格小于 δ 的对，然后将该距离分配给 δ。
返回 δ。 预先感谢您。
Can someone please explain to me why the recursive part of this algorithm has the runtime
T(n) = {O(1), if n ≤ 3;
{Tf(n/2) + Tc(n/2) + O(n), if n > 3.
->where Tf(n/2) represents the floor function of T(n/2) and Tc(n/2) represents the the ceilling function????
The algorithm is called Shamos and the main steps are:
- If n ≤ 3 find the closest points by brute force and stop.
- Find a vertical line V such that divides the input set into two disjoint subsets PL and PR of size
as equal as possible . Points to the left or on the line
belong PL and points to the right or on the line belong to PR. No point belongs to both since
the sets are disjoint. - Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest
pair in PR. Let δ = min(δL, δR). The distance of a pair of closest points in the input set P is either that of
the points found in the recursive step (i.e., δ) or consists of the distance between a point in PL
and a point in PR.(a) The only candidate points one from PL and one from PR must be in a vertical strip consisting
of a line at distance δ to the left of the line V and a line at distance δ to the right of V(b) Let YV be an array of the points within the strip sorted by non-decreasing y coordinate
(i.e., if i ≤ j then YV [i] ≤ YV [j]).(c) Starting with the first point in YV and stepping trough all except the last, check the distance
of this point with the next 7 points (or any that are left if there are not as many as 7). If a
pair is found with distance strictly less than δ then assign this distance to δ.Return δ.
Thank you in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
T(c(n/2))和T(f(n/2))描述了在左右组上递归调用算法需要多少时间，因为一半的分数已被放置在每组中。O(n)来自算法的棘手部分：在递归调用之后，我们找到了 δ，即左组或右组中最近的一对点之间的距离。现在我们想要寻找由左组中的一个点和右组中的一个点组成的对。当然，查看距离中线超过 δ 的点几乎没有什么用处。然而，所有点仍然可能都在中线的 δ 范围内，因此看起来我们必须比较n^2点对。现在重要的观察是，正是因为我们知道在每个组中，没有一对点比 δ 更近，所以我们知道，对于我们需要查看的正确组中的点数量，存在一个小的、恒定的最坏情况限制对于左组中的每一对。因此，如果我们只能将点按 y 坐标排序，我们就可以在线性时间内找到最接近的对。由于列表在递归调用之间传递的方式，可以在线性时间内获得这个排序列表，但细节我不明白（任何人都可以随意填写）。T(c(n/2))andT(f(n/2))describe how much time it takes to call the algorithm recursively on the left and right groups, respectively, since half of the points have been placed in each group.O(n)comes from the tricky part of the algorithm: after the recursive calls, we have found δ, namely the distance between the closest pair of points either in the left group or in the right group. Now we want to look for pairs consisting of one point from the left group and one point from the right group. Of course, there is little use in looking at points that are further away than δ from the middle line. However, it could still be that all points are within δ of the middle line, so it looks like we risk having to comparen^2point pairs. The important observation now is that precisely because we know that in each group, no pair of points is closer than δ, we know that there is a small, constant worst-case limit to how many points from the right group we need to look at for each pair in the left group. So if we can only get our points sorted on their y-coordinates, we can find the closest pair in linear time. It's possible to obtain this sorted list in linear time due to the way the list is passed between the recursive calls, but the details escape me (feel free to fill in, anyone).