Turtle和Rabbit算法总是O(N)吗？

Question

我将在前面加上一个事实,即我对Big O Notation并不完全了解,所以也许我对此的想法是关闭的.

当我遇到一个关于在链接列表中检测无限循环的问题时,我随机浏览了它.这让我想到了这里称为Turtle and Rabbit 的算法.

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)意味着算法的速度与列表中的元素数量呈线性增长.

但是,除非我看错了,兔子变量总是跳过1个节点(所以它"更快"),这意味着它有可能跳过乌龟节点,因此有可能围绕无限循环1循环或者在它变成与turtle变量相同的节点之前或更多次,这意味着最坏情况不是O(N).

我错过了什么吗？我想一个优化可能是检查是否rabbit.Next.Equals(turtle)也是如此,因为没有任何评论指出这一点所以我想知道我是否遗漏了一些东西.

Answer 1

兔子永远不会跳过乌龟,因为速度之间的差异是1.

兔子首先进入循环,然后是乌龟.一旦乌龟进入循环,兔子和乌龟的差异就会确定,你可以认为兔子是乌龟的背后.然后,每个步骤的差异简单地减少1.

因此总步数不会超过N,因此它是O(n).