攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

Algorithm 演算法 - 判圈系列 Brent 判圈算法(傳送龜算法)

Brent's Cycle Detection Algorithm (The Teleporting Turtle)

攻城獅's photo
攻城獅
·Jun 10, 2022·

Subscribe to my newsletter and never miss my upcoming articles

Play this article

簡介 Intro

image.png

根據演算法期會比 Floyd 的方式快 24-36% 的速度。

解釋

這個演算法的方式其實基本上跟 Floyd 不一樣的地方在於龜兔的移動方式。在 Floyd 的演算法中,龜兔會一起移動,只是步數的不同。但在 Brent 的演算法中,只有兔子在移動。

每次兔子移動後,烏龜會馬上傳送到跟兔子一樣的位置(所以才叫 Teleporint Turtle)。然後兔子在將步數倍增移動。例如兔子第一次移動 1 格、再來 2 格、4 格一直走到底或是遇到烏龜。

進階題目

找出迴圈長度

當相遇時,兔子從原本位置走到烏龜的位置就是迴圈的長度。為什麼呢?因為當兔子要開始走的時候,假設位置是 x,烏龜會需要先瞬移到兔子現在的位置 x。而兔子從 x 走到烏龜的位置,不就是整整繞了一圈嗎?因此當下兔子走的步數就是迴圈的長度

def detectCycle(self):
    # if head is null
    # then no loop
    temp = self.head

    if not (temp):
        return False
    tortoise = temp
    hare = temp.next
    power = 1
    length = 1

    # This loop runs till we
    # find the loop. If there
    # is no loop then second
    # pointer ends at NULL
    while hare and hare != tortoise:

        # condition after which
        # we will update the power
        # and length as smallest
        # power of two gives
        # the start of cycle.
        if length == power:

            # updating the power.
            power *= 2

            # updating the length
            length = 0

            tortoise = hare

        hare = hare.next
        length += 1
    # if it is null then no loop
    if not (hare):
        return

找出迴圈連結點

要找出連結點的話,在找出迴圈長度後。只要將兔子放回開頭,而烏龜放到從起點走回圈長度的距離(就是 length + 1)。之後兩個同時一步一步走,走到相遇就是起點了。

這邊要來講說為什麼,發現網路上都只跟我說這樣就好,但原理還是要理解才不容易忘。

假設迴圈長度 C、起點到迴圈連接點的長度是 L。然後從連接點到烏龜的點是 A,烏龜的位置到連接點長度是 B

A + B = C
A = C - L
C - L + B = C
C - C + B = L
B = L

所以就是 BL 喔(笑


    # Now set tortoise pointer
    # to the beginning and
    # hare pointer to
    # beginning plus cycle
    # length which is length.
    tortoise = hare = self.head
    while length > 0:
        hare = hare.next
        length = length - 1

    # Now move both pointers
    # at same speed so that
    # they meet at the
    # beginning of loop.
    while hare != tortoise:
        hare = hare.next
        tortoise = tortoise.next

    return tortoise

Reference

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this

Impressum

As smiple as possible