- PR -

アルゴリズムパズル（リンクリスト）

«前のページへ 1|2|3|4|5 次のページへ»
投稿者投稿内容
囚人
ぬし
会議室デビュー日: 2005/08/13
投稿数: 1019
投稿日時: 2005-11-16 14:30
引用:

いえ、この場合の計算量は n に対して完全に比例関係にあるので、n が無限の場合でも O(n) は成り立ちます。
ただし、O(n) も無限ですが。。。

すみません。
引用:

しかし、無限ならば O(n)ではないですね･･･。

の「無限」は
引用:

スキャンに無限の時間がかかるなら、リストは循環参照

の無限にかけてました。
n が有限の場合で循環参照している場合に、O(n) が無限になると駄目ですねって事でした。


_________________
囚人のジレンマな日々
cats
大ベテラン
会議室デビュー日: 2002/11/29
投稿数: 221
お住まい・勤務地: 東京
投稿日時: 2005-11-16 14:33
最初の方で答えが出ていますが。

bool IsDangling(List l)
{
List p = l;
while (l != null && l != (p = p.next))
{
l = l.next;
p = p.next;
}
return l != null;
}

ループの長さがmとします。
ループの入り口には、n-m回でたどり着きます。
また、lとpは1回のループで1つずつ ずれていきますので、およそm-1回で同じになります。

また、終端しててもn-1回で終了しますので、O(n)です。
囚人
ぬし
会議室デビュー日: 2005/08/13
投稿数: 1019
投稿日時: 2005-11-16 14:41
>cats さん
え？混乱してきた〜。
1(2)->2(3)->3(4)->4(2)･･･
※()内は次のノード
l･･･1
p･･･2

l･･･2
p･･･3

l･･･3
p･･･4

l･･･4
p･･･2

l･･･2
p･･･3
となって無理なような気が･･･。間違い指摘して下さい。

_________________
囚人のジレンマな日々
zar
会議室デビュー日: 2005/11/16
投稿数: 1
投稿日時: 2005-11-16 14:46
>ポインタを２つ用意して追いかけっこする。
わかりにくいけどこれが正解じゃない？

大体以下のような感じ。
リストの末尾はNULLとします。

typedef struct Node_{
void* data; /*テキトー*/
struct Node_* next;
}Node;

/* 循環しているなら1, そうでないなら0を返す */
int is_circular_list(Node* seq)
{
Node* rabbit = seq;
Node* tortoise = seq;
while(rabbit && tortoise && rabbit->next) {
tortoise = tortoise->next;
rabbit = rabbit->next->next;
if(rabbit == tortoise) {
return 1;
}
}
return 0;
}
cats
大ベテラン
会議室デビュー日: 2002/11/29
投稿数: 221
お住まい・勤務地: 東京
投稿日時: 2005-11-16 14:51
囚人さんへ
(1,2)、(2,4)、(3,3)で同じになって循環参照の判定です。

（p != nullの判定が抜けていてバグっていますね）
まーちん
会議室デビュー日: 2001/12/10
投稿数: 5
投稿日時: 2005-11-16 14:52
リンクをたどりながら、ポインタをハッシュテーブルに格納していけば良いのでは？
ハッシュテーブルなら、O(1)で検索できますし。
MMX
ぬし
会議室デビュー日: 2001/10/26
投稿数: 861
投稿日時: 2005-11-16 14:53
感動
互いに素な、歩幅の忍者を放ち、後ろから追突したら ループ有。
kanai
ベテラン
会議室デビュー日: 2004/09/13
投稿数: 98
投稿日時: 2005-11-16 15:00
kanaiです。

再帰を使って、こんな感じでいかがでしょうか？（VB.NET）

簡単のため、リンクリストはInteger配列として実装し、
リストの先頭は添字0、リストの末尾は値-1で表しています。

コード:

 Module Module1



    Sub Main()

        Dim loopedlist() As Integer = {2, 3, 4, -1, 0}

        Console.WriteLine(IsLooped(loopedlist, 0))

        Dim nolooplist() As Integer = {2, 3, 4, -1, 1}

        Console.WriteLine(IsLooped(nolooplist, 0))



        Console.ReadLine()

    End Sub



    Private Function IsLooped(ByVal list As Integer(), ByVal index As Integer) As Boolean

        Debug.WriteLine("list(" & index.ToString & ")=" & list(index))

        If list(index) = -1 Then

            Return False

        ElseIf list(index) = 0 Then

            Return True

        Else

            Return IsLooped(list, list(index))

        End If

    End Function



End Module


[ メッセージ編集済み 編集者: kanai 編集日時 2005-11-16 15:01 ]
«前のページへ 1|2|3|4|5 次のページへ»

スキルアップ／キャリアアップ（JOB@IT）