Алгоритм Черепаха и Кролик всегда O (N)?

Question

Я собираюсь предвосхитить это тем фактом, что я не полностью разбираюсь в нотации Big O, поэтому, возможно, мои мысли об этом не верны.

Я случайно просматривал SO, когда натолкнулся на вопрос об обнаружении бесконечных циклов в связанных списках. Это указало мне на алгоритм здесь , известный как Черепаха и Кролик.

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).

Answer 2

Небольшое ручное моделирование должно показать вам, что хотя кролик может пропустить черепаху один раз, второй раз по кругу, он наступит на нее (так сказать).(РЕДАКТИРОВАТЬ: это применяется, когда и кролик, и черепаха находятся в цикле, что будет происходить в большинстве O (N) итераций.) Поскольку O (2 * N) = O (N), это все еще алгоритм O (N).

Хороший алгоритм тоже.+1 за ссылку.

Answer 3

Кролик не может перепрыгнуть через черепаху, так как черепаха тоже движется.В искусстве ASCII:

R _ T
    R T
        X

Иными словами, пока кролик находится за черепахой, каждая итерация цикла уменьшает их расстояние на 1. Следовательно, будет итерация, в которой расстояние становится равным 0.

Answer 4

Этот алгоритм становится понятнее, если вместо этого вы запустите кролика и черепаху на одном узле. Когда черепаха переместилась на N узлов вперед, кролик переместился на 2N узла вперед. Если есть цикл длины N, черепаха вернется в начальную точку после N ходов, и 2N ходы кролика также посадят его в начальный узел, дважды пройдя круг.

Answer 5

Есть две ситуации:

1. Есть четное количество узлов, а
2. Существует нечетное количество узлов.

Давайте рассмотрим оба.

В 1 мы имеем это:

T R x x затем x T x R затем x R T x затем x x x RT

В 2 у нас есть это: T R x затем R T x затем x x RT

Учитывая, что кролик и заяц могут двигаться только с максимальными приращениями в два, это только два условия, которые стоит отметить. Возможно, здесь есть правильное индуктивное доказательство, но показ этапов объясняет, почему это работает, даже если кролик пропускает черепаху. Кролик может пропустить черепаху, только если он позади черепахи, и если он позади черепахи, либо он не пропустит, либо столкнется.

Когда кролик пропускает черепаху, как в 1, нам нужно только N+1 ходов черепахи и кролика, поэтому 2N+2 для N - длина списка, равная O(N)