algorithm - 在未排序的数组中查找特定比率。时间复杂度

Question

这是家庭作业。

目标是用伪代码呈现一种算法，该算法将搜索数字数组(不指定整数或 >0)并检查任意两个数字的比率是否等于给定的 x。时间复杂度必须在 O(nlogn) 以下。

我的想法是对数组进行合并排序(O(nlogn) 时间)，然后如果 |x| > 1 开始按降序检查每个数字(使用二进制遍历算法)。检查还应该为每个数字花费 O(logn) 时间，最坏的 n 次检查的总时间为 O(nlogn)。如果我没有遗漏任何东西，这应该会在赋值参数内给出最坏情况 O(nlogn) + O(nlogn) = O(nlogn)。

我意识到排序后从哪里开始检查比率并不重要，但时间成本会按 1/2 摊销)。

我的逻辑正确吗？有没有更快的算法？

如果不清楚，举个例子:

给定一个数组 { 4, 9, 2, 1, 8, 6 }

如果我们想搜索比率为 2 的值:

1. 归并排序 { 9, 8, 6, 4, 2, 1 }

2. 由于给定的比率 >1，我们将从左到右搜索。

2a。第一个数字是 9。检查 9/4 > 2。检查 9/6 < 2 下一个数字。2b.第二个数字是 8。检查 8/4 = 2。完成

Answer 1

您提供的分析是正确的，是解决此问题的完美方法。排序确实在时间 O(n log n) 内起作用，2n 二进制搜索也需要 O(n log n) 时间。也就是说，我认为您不想在这里使用术语“摊销”，因为它指的是不同类型的分析。

关于如何稍微加快您的解决方案的提示，您的解决方案的总体思路是可以针对任何数字高效地查询该数字是否存在于数组中。这样，您就可以遍历所有数字并寻找任何可以使比率有效的东西。但是，如果您在支持快速访问的数组之外使用辅助数据结构，则可能会以增加内存使用量为代价来减少运行时间。尝试考虑哪些数据结构支持非常快速的访问(例如，O(1) 查找)，看看您是否可以在这里使用它们中的任何一个。

希望这对您有所帮助!