运行时解释 [英] Runtime explanation

问题描述

有人可以给我解释一下为什么这个算法的递归部分具有运行时

T（N）= {O（1），如果n≤3;        {铁蛋白（N / 2）+ TC（N / 2）+ O（N），如果n> 3。

- >其中铁蛋白（N / 2）重presents T（N / 2）和TC（N / 2）的整函数重新presents中的ceilling功能????

该算法被称为Shamos和主要步骤是：

1. 如果N≤3找到最接近的点用暴力和​​停止。
2. 找到一条垂直线v的将输入设置为两个不相交的子集PL和大小的公关 尽可能相等。指向左侧或上线 属于PL并指向右侧或上线属于公关。没点同时属于自 该集是不相交的。
3. 递归找到接近的一对点的PL的距离δL和的距离的接近的δR 对公关。

4. 让δ=分钟（δL，δR）。一对接近的点的输入集P的距离是要么的 在递归步骤中找到的点（即，δ）或由其组成的距离在PL的点之间 和公关点。

   （一）的唯一候选点1从PL与一个来自PR必须在垂直条组成 一行在距离δ的线V的左侧和线在距离δ为V的权

   的

   （二）设YV是点的条依非递减y坐标内的阵列 （即，如果我≤Ĵ然后YV [I]≤YV [J]）。

   （三）开始在YV第一点和步进低谷所有除最后，检查的距离 的这一点上与下一个7点（或任何被留下，如果有不多达7）。如果一个 对被发现的距离比严格δ小于分配这个距离δ。

5. 返回δ。 谢谢你在前进。

解决方案

T（C（N / 2））和 T（F（的n / 2））描述多少时间才能调用算法递归地在左侧和右组，分别因为一半的点已被放置在每个组中的

O（N）来自算法的棘手的部分：递归调用后，我们发现δ，即最接近对点无论是在之间的距离左组或在右组中。现在，我们要寻找对包括从左侧组中的一个点，并从右侧组中的一个点。当然，在看那些远于从中线δ点用处不大。但是，它仍然可能是所有的点都在δ中间线的，所以看起来我们很可能有比较 N ^ 2 点对。一个重要的发现是，现在precisely，因为我们知道，每个组中，没有对点比δ接近，我们知道有一个小的，恒定的最坏情况限制多少百分点，我们需要正确的组看每对在左侧组。因此，如果我们只能得到排序他们的Y坐标我们的观点，我们可以找到最接近的一对线性时间。这是可能获得此排序列表中的线性时间，由于该列表通过递归调用的方式，但细节逃避我（随意填写，任何人）。

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:

1. If n ≤ 3 find the closest points by brute force and stop.
2. 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.
3. Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest pair in PR.

4. 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 δ.

5. Return δ. Thank you in advance.

解决方案

T(c(n/2)) and T(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 compare n^2 point 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).

这篇关于运行时解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！