algorithm - 停在无限街道上的汽车：找到汽车并计算复杂性

Question

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

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

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

Answer 1

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

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

Answer 2

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