Użytkownik "Wojciech "Spook" Sura"
<wojciech.sura_no@spam_poczta.medi.com.pl> napisał w wiadomości
news:op.vw3s6w1gppa1dq@l3.medicom.local...

>Kolega zaproponował zadanie: w jaki sposób odnaleźć cykl w liście
>jednokierunkowej nie niszcząc jej, zachowując stałe zużycie pamięci i w
>czasie liniowym?
>
>Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
>umiem zejść do stałego. Macie jakieś pomysły?
>
>Pozdrawiam -- Spook.

Tak na mój pierwszy rzut oka, to jeśli nie znamy z góry rozmiaru
listy to się nie da. W czasie liniowym i przy z góry założonym maksymalnym
zużyciu pamięci to nie da sięnawet ze 100% pewnością stwierdzić, czy
lista w ogóle ma cykl. To tak jak chodzić po labiryncie i mieć wiaderko
z ograniczoną liczbą okruchów chleba do zaznaczania odwiedzonych
komnat. Ja tu widzę co najmniej potrzebę pamięci rzędu o(log(n)) do
zaznaczania obszarów już odwiedzonych, czy też 'stawiania wartowników'.
Imo sprawa się uprości, jeśli założymy, że cykl może mieć nie więcej niż
k. Wtedy da się zastosować algorytm systematycznego 'zamykania' obszarów
listy które na pewno nie należą do cyklu i potrzeba pamięciowa
jest wtedy stała o(k).