分而治之算法（应用二进制搜索？！）

我是新来的。作为一名研究生，我现在已经对算法进行了头脑风暴。我感谢任何可以延伸的关于下面问题的帮助。我已经搜索了足够的，我找不到解决这个问题的任何解决方案。分而治之算法（应用二进制搜索？！）

我们有一个无限长的排序不同数字的数组。前n个数字是大于0但小于1的分数。所有其余元素都是“1”，而您没有给出n的值。您需要开发一种算法来检查用户给定分数F是否出现在该数组中。作为n的函数分析算法的时间复杂度。（n = 8的示例，其中1从数组的第8个位置开始）

我的方法：我在猜测解决此问题的最佳方法是使用二分搜索。每次我们都可以将数组的大小减半，最后到达要找到的分数。让我们假设阵列中有m个元素，包括1的元素。小数元素的数量是n。对整个数组执行二分搜索的时间复杂度为O（log（m））。因为我被要求用n来表示时间复杂度，所以m = n + k（假设阵列中1的数量是k）所以这个问题的时间复杂度是O（log（n + k））。

请抛开你的想法。谢谢

来源

2015-02-08 whyme

“我们有一个无限长的排序不同数字的数组。”停在那儿。现在离开计算机科学部门，去隔壁的数学系。 – 2015-02-08 15:52:54

@MikeNakis为什么？一些计算机科学算法需要假定非绑定值。 – ElderBug 2015-02-08 15:54:18

你不能有一个无限长度的数组。你可能会说到无尽的物品流，但不是无限的阵列。当然，您不能在流上执行二分搜索，因为您需要知道项目的总数，以便可以计算中间值等等。 – 2015-02-08 15:57:46

你确实可以通过指数搜索来解决无限数组，即不知道m。

尝试第一个元素并将索引加倍，直到得到1为止。这将花费O（Lg n）个步骤。然后，您切换到二进制搜索，并在更多的O（Lg n）步骤中获得答案。

k的值是无关紧要的。

这种方法在现实世界中是有意义的，也就是说，对于有限但未知大小的数组，假设至少有一半的数组填充了1，以便搜索终止入界。

来源

2015-02-08 16:05:48

在实践中，你在你的指数搜索中甚至不会到1，只能到达> F的第一个元素。而且你只能在该位置和前一位置之间进行二进制搜索。当然，这不会影响最坏的情况下的时间复杂性，但它可以给你一个更好的平均情况。 – biziclop 2015-02-08 16:10:46

谢谢。有道理:) – whyme 2015-02-08 16:13:28

@biziclop：对。复杂度实际上是O（Lg i），其中i是搜索到的元素的索引。另外，我没有说二分查找必须从第一个元素开始:)但这种优化并没有改善平均情况，仍然是O（Lg n）或O（Lg i），它只能保留单个测试。 – 2015-02-08 16:21:11

分而治之算法（应用二进制搜索？！）

回答

相关问题