algorithm - 乌龟和兔子算法总是 O(N) 吗？

Question

我要先说明我对大 O 表示法并不完全了解，所以也许我对这个的想法是错误的。

当我遇到一个关于检测链接列表中的无限循环的问题时，我随机浏览了 SO。这让我想到了算法 here被称为乌龟和兔子。

class Node {
  Node next;
}

boolean isInInfiniteLoop(Node node) {
  if (node == null) {
    return false;
  }
  Node turtle = node; // slower moving node
  Node rabbit = node.next; // faster moving node
  while (rabbit != null) {
    if (rabbit.equals(turtle)) {
      // the faster moving node has caught up with the slower moving node
      return true;
    } else if (rabbit.next == null) {
      // reached the end of list
      return false;
    } else {
      turtle = turtle.next;
      rabbit = rabbit.next.next;
    }
  }
  // rabbit reached the end
  return false;
}

他在文章中提到它是 O(N)。据我了解，O(N) 意味着算法的速度与列表中的元素数量成线性关系。

但是，除非我看错了，否则 rabbit 变量总是跳过 1 个节点(因此它“更快”)，这意味着它有可能跳过 turtle 节点，从而有可能绕着在它成为与 turtle 变量相同的节点之前无限循环 1 次或更多次，这意味着最坏的情况不是 O(N)。

我错过了什么吗？我想一个优化可能是检查 rabbit.Next.Equals(turtle) 是否也一样，但由于没有评论指出这一点，所以我想知道我是否遗漏了什么。

Answer 1

兔子永远不会跳过乌龟，因为两者的速度相差1。

兔子先进入循环，然后是乌龟。乌龟一进入循环，就决定了兔子和乌龟的区别，可以认为兔子在乌龟后面。然后就是差值每一步简单地减 1。

所以总步数不会超过N，因此是O(n)。