algorithm - Turtle and Rabbit算法是否总是O(N)？

我将以我对Big 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个节点(因此它“更快”)，这意味着它有可能跳过乌龟节点，从而有可能在无限循环1中循环或多次与乌龟变量成为同一节点之前，这意味着最坏的情况不是O(N)。

我想念什么吗？我猜一个优化可能是检查rabbit.Next.Equals(turtle)是否也是如此，但是由于没有注释指出这一点，所以我想知道我是否丢失了一些东西。

最佳答案

兔子永远不会跳过乌龟，因为速度之差为1。

兔子先进入循环，然后再进入乌龟。乌龟进入循环后，就决定了兔子和乌龟的区别，您可以认为兔子在乌龟后面。然后，对于每个步骤，差只是简单地减少1。

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

关于algorithm - Turtle and Rabbit算法是否总是O(N)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5834198/