首先让我说出正确的问题:
问:有一个文件包含超过一百万个点(x,y),每个点代表一个星.在(a,b)有一个行星地球.现在,任务是建立一个算法,将100颗最接近的恒星归还地球.什么是你的算法的时间和空间复杂性.
在各种访谈中多次询问过这个问题.我试着查找答案,但找不到满意的答案.
一种方法,我认为可能使用大小为100的最大堆.计算每个星的距离,并检查距离是否小于最大堆的根.如果是,请将其替换为root并调用heapify.
还有其他更好/更快的答案吗？
PS:这不是一个家庭作业问题.
tem*_*def 28
你可以在时间O(n)和空间O(k)中实现这一点,其中k是你想要的最接近点的数量,通过使用一个非常聪明的技巧.
的选择问题是如下:给定元件的阵列和一些索引i,重新排列所述阵列,使得第i个元素是在正确的位置,比所述第i个元素更小的所有元素都向左侧的元素,并且所有元件更大比第i个元素更右边.例如,给定数组
40 10 00 30 20
如果我尝试基于索引2(零索引)进行选择,则可能会得到一个结果
10 00 20 40 30
由于索引2(20)处的元素位于正确的位置,因此左侧的元素小于20,右侧的元素大于20.
事实证明,由于这不是一个比实际排序数组更严格的要求,因此可以在时间O(n)中执行此操作,其中n是数组的元素数.这样做需要一些复杂的算法,如中位数算法,但实际上是O(n)时间.
那么你怎么在这里使用它？一种选择是将文件中的所有n个元素加载到数组中,然后使用选择算法在O(n)时间和O(n)空间(此处,k = 100)中选择前k个.
但你实际上可以比这更好!对于你想要的任何常数k,保持2k元素的缓冲区.将2k元素从文件加载到数组中,然后使用选择算法重新排列它,使得最小的k个元素位于数组的左半部分,最大的元素位于右侧,然后丢弃最大的k个元素(它们可以' t是k个最近点中的任何一个).现在,将更多元素从文件加载到缓冲区中并再次执行此选择,并重复此操作直到您处理完文件的每一行.每次进行选择时,都会丢弃缓冲区中最大的k个元素,并保留到目前为止看到的k个最近点.因此,在最后,您可以最后一次选择前k个元素并找到前k个.
新方法的复杂性是什么？那么,你正在使用O(k)内存作为缓冲区和选择算法.最后,在大小为O(k)的缓冲区上调用select总共O(n/k)次,因为在读取k个新元素后调用select.由于在大小为O(k)的缓冲区上选择花费时间O(k),因此这里的总运行时间是O(n + k).如果k = O(n)(合理的假设),则需要时间O(n),空间O(k).
希望这可以帮助!