Floyd의 주기 찾기 알고리즘이 연결 목록의 루프를 효율적으로 감지합니까?

Floyd의 순환 찾기 알고리즘을 사용하여 연결 목록에서 루프 감지

컴퓨터 과학의 기본 데이터 구조인 연결 목록은 일련의 요소를 나타내는 데 자주 사용됩니다. 특정 시나리오에서는 연결된 목록에 마지막 노드가 이전 노드를 다시 가리키는 루프가 포함되어 순환 구조를 만드는 것이 가능합니다. 이러한 루프의 존재를 식별하는 것은 연결된 목록과 관련된 다양한 작업에서 중요한 작업입니다.

Floyd의 주기 찾기 알고리즘

거북이와 토끼 알고리즘이라고도 알려진 Floyd의 주기 찾기 알고리즘은 다음을 제공합니다. 연결된 목록에서 루프를 감지하는 효율적인 방법입니다. 알고리즘은 목록을 통해 서로 다른 속도로 두 개의 포인터(참조)를 이동하는 원리를 기반으로 작동합니다.

1. Tortoise(느린 포인터): 한 번에 한 노드씩 앞으로 이동합니다.
2. 토끼(빠른 포인터): 한 번에 두 개의 노드를 앞으로 이동합니다.

원리:

• 루프 있음: 목록에 루프가 있으면 거북이와 토끼는 결국 동일한 노드에서 만나 루프가 있음을 나타냅니다.
• 루프 없음 : 목록에 루프가 없으면 거북이나 토끼가 목록의 끝에 도달하여(널 포인터) 루프가 없음을 알립니다.

Java 구현

다음 Java 함수는 Floyd의 주기 찾기 알고리즘을 구현합니다.

<code class="java">boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}</code>

장점

Floyd의 주기 찾기 알고리즘은 다음과 같은 장점을 제공합니다.

• 일정한 공간 복잡도: 두 개의 포인터(참조)만 필요하므로 공간 복잡도가 일정합니다(O(1)).
• 선형 시간 복잡도: 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 연결 목록의 노드 수입니다.

위 내용은 Floyd의 주기 찾기 알고리즘이 연결 목록의 루프를 효율적으로 감지합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!