在时间复杂度 O(n) 的无限线上找到一个点的算法

Question

在无限直线上有一个位置未知的点 x。一个算法应该找到这个点的时间复杂度为 O(n)，其中 n 是搜索起点 s 和 x 之间的距离。这条线被分成几步。每一步的长度都相同。

我的想法是这样的:

start in s
go 1 step left
if x found { 
    terminate
 }
else {
    go 2 steps right
    if x found { 
        terminate
    }
    else {
        go 3 steps left
        ...
        ..
        .
    }
}

但这并不像 O(n) 那样接缝。

有什么想法吗？

谢谢

Answer 1

您已经找到了适合这项工作的算法。

But this doesn't seam like O(n).

这个算法是精确的 O(n)，因为对于 1 和 n 之间的每个 k 值，它恰好探测两次 - 一次在右边的位置 x+k*sm，一次在左侧位置 x-k*s。这意味着该算法是 O(2n)，但由于在大 O 表示法中始终排除常数因子，因此您的算法是 O(n)。