2

这是面试时被问到的问题:

你被放置在一条很长的街道上。这是您停放汽车的街道。你必须在这条街上找到你的车。

找到您的汽车的算法是什么,复杂性是什么。他们正在寻找的答案是 O(nlogn)...但是您必须证明为什么它是 o(nlogn)... 提示:要获得这​​个答案涉及很多数学。

4

2 回答 2

5

我想n这里是到汽车的距离。问题是你在一条无限的街道/线的中间,你不知道往哪个方向走。

对此的解决方案是在一个方向上移动 x 个单位,然后向另一个方向移动 2x,然后向前移动 4x,反向移动 8x 等等......所需的步行是O(n*logn) O(n)。

于 2012-08-29T22:42:26.893 回答
0

这是网上牛路径问题的一个特例。通常的度量标准是最坏情况下的行驶距离与如果您知道汽车在哪里(竞争比率)将行驶的距离相比。这是 9n,实际上是 O(n),而不是 O(n log n)。但是,您可以进行 O(log n) 方向的更改。

于 2012-08-29T23:06:41.823 回答