Блог

Я собираюсь предварить это тем фактом, что я не совсем разбираюсь в нотации 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) означает, что скорость алгоритма линейно растет в зависимости от количества элементов в списке.

Однако, если я не ошибаюсь, переменная rabbit всегда пропускает 1 узел (так что это «быстрее»), что означает, что у нее есть потенциал пропустить узел turtle, таким образом, имея возможность повторять бесконечный цикл 1 или более раз, прежде чем она станет тем же узлом, что и переменная turtle, что означало бы, что наихудший сценарий — это не O (N).

Я что-то упускаю? Я предполагаю, что оптимизация может заключаться в том, чтобы также проверить, rabbit.Next.Equals(turtle) ли это, но поскольку ни один из комментариев не указывает на это, мне интересно, не упускаю ли я чего-то.

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

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

Таким образом, общее количество шагов не превысит N, и, следовательно, оно равно O (n).

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

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

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

 R _ T
    R T
        X
  

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

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

Возможны две ситуации:

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

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

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