- PR -

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

«前のページへ 1|2|3|4|5 次のページへ»
投稿者投稿内容
渋木宏明(ひどり)
ぬし
会議室デビュー日: 2004/01/14
投稿数: 1155
お住まい・勤務地: 東京
投稿日時: 2005-11-16 13:30
引用:

アルゴリズムの計算量が、その n に比例するようなアルゴリズムであるならば、O(n) だ、というわけでなないのかな･･･？（多分）


なら、単純に

・リストを先頭からスキャン開始！
→スキャンに無限の時間がかかるなら、リストは循環参照。
→有限な時間内にスキャンが完了すれば、リストは循環参照ではない。

という「数学的」な回答に落ち着いてしまうような。。。

_________________
// 渋木宏明 (Hiroaki SHIBUKI)
// http://hidori.jp/
// Microsoft MVP for Visual C#
//
// ＠ＩＴ会議室 RSS 配信中: http://hidori.jp/rss/atmarkIT/
なか-chan@最愛のiMac
ぬし
会議室デビュー日: 2002/07/17
投稿数: 385
お住まい・勤務地: 和光市・世田谷区
投稿日時: 2005-11-16 13:42
アドレスの最小値を保存しておき
同じアドレスが出るか、最後にnullが出たら終了
ではどうでしょうか？

↑ダメダメでした。m(__)m

[ メッセージ編集済み 編集者: なか-chan 編集日時 2005-11-16 15:56 ]
渋木宏明(ひどり)
ぬし
会議室デビュー日: 2004/01/14
投稿数: 1155
お住まい・勤務地: 東京
投稿日時: 2005-11-16 13:48
引用:

アドレスの最小値を保存しておき
同じアドレスが出るか、最後にnullが出たら終了
ではどうでしょうか？


途中からループしていて、ループに突入する前に最小値が出てくるパターンだとＮＧかと。

「アドレス値最小」には大して意味が無いと思うので、その方向でいくならノードの全部の値を記憶しておいて、１個進むたびに既出かどうかチェックすることになるんじゃないかな？（って、これ既出か）

_________________
// 渋木宏明 (Hiroaki SHIBUKI)
// http://hidori.jp/
// Microsoft MVP for Visual C#
//
// ＠ＩＴ会議室 RSS 配信中: http://hidori.jp/rss/atmarkIT/
囚人
ぬし
会議室デビュー日: 2005/08/13
投稿数: 1019
投稿日時: 2005-11-16 13:51
引用:

・リストを先頭からスキャン開始！
→スキャンに無限の時間がかかるなら、リストは循環参照。
→有限な時間内にスキャンが完了すれば、リストは循環参照ではない。

ありですねぇ〜^^
しかし、無限ならば O(n)ではないですね･･･。

n が不明であっても、バブルソートは実行できて、且つ計算量（最悪の）は O(n^2) です。
同じように、問題は「そのアルゴリズムが n の個数が明確である事を前提としてはならない」という意味ではないんですかね。
で、計算中に個数を数えるのはアリなんでしょうけど、循環参照していた場合、その個数が数えられないので、ん〜･･･。

_________________
囚人のジレンマな日々
でっち６号
大ベテラン
会議室デビュー日: 2005/01/31
投稿数: 176
お住まい・勤務地: Kawasaki
投稿日時: 2005-11-16 13:54
こんにちは、でっちです。

スミマセン、なんでnが不明だとNGなのか本気で分らないです
自分ではそのまま判定できるつもりでした。

言語不定ですが、こんな感じのロジックで考えました。
コード:

※listが単方向リストの構造体、次のポインタを示す要素nextを持つ。

　リストの終端では、nextはnullになる。

bool RoopCheck(list){

    counter = 0;      //通ったリストの個数

    maxpointer = 0;   //参照したリストの最大ポインタ

    pointer = 0;



    //リストの最後までループ

    while (list[pointer].next != null){

        //カウンタが最大ポインタを超えた場合循環参照している

        if (counter > maxpointer){

            return false;

        }

        //参照ポインタの最大値を設定

        if (list[pointer].next > maxpointer){

            maxpointer = list[pointer].next;

        }

        pointer = list[pointer].next;

        counter++;

    }

    return true;

}


[根拠]
ループのある時点での最大ポインタをaとすると、その時点で循環参照せずに
リストを組み立てる際に使用できるリスト個数の最大値はa+1になる。
よって、ループした回数(=参照したリストの個数)がそれを超えていた場合は
循環参照していることになる。

問題点のご指摘をお願いします m(_ _)m


[ メッセージ編集済み 編集者: でっち６号 編集日時 2005-11-16 14:21 ]
渋木宏明(ひどり)
ぬし
会議室デビュー日: 2004/01/14
投稿数: 1155
お住まい・勤務地: 東京
投稿日時: 2005-11-16 14:00
引用:

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


いえ、この場合の計算量は n に対して完全に比例関係にあるので、n が無限の場合でも O(n) は成り立ちます。
ただし、O(n) も無限ですが。。。
一郎
ぬし
会議室デビュー日: 2002/10/11
投稿数: 1081
投稿日時: 2005-11-16 14:20

引用:

渋木宏明(ひどり)さんの書き込み (2005-11-16 13:48) より:
ノードの全部の値を記憶しておいて、１個進むたびに既出かどうかチェックすることになるんじゃないかな？（って、これ既出か）

私もこれくらいしか思いつきませんけど、そうすると1つのノードに対してn-1回のチェックが必要になるんですよね。
だからどうなるんだろ。O(n2乗)かな。

引用:

でっち６号さんの書き込み (2005-11-16 13:54) より:
ループのある時点での最大ポインタをaとすると、その時点で循環参照せずに
リストを組み立てる際に使用できるリスト個数の最大値はa+1になる。

最大ポインタというのはメモリ上のアドレスということですかね。（0xFFFFFF8Bとか）
参照を数値で表していない言語ではどうするんですか？C#とか。Javaもかな。
それに、O(n)にはならないですよね。「メモリアドレス空間の大きさに比例する」かな？
ゆう
ベテラン
会議室デビュー日: 2003/06/20
投稿数: 56
投稿日時: 2005-11-16 14:23
引用:

でっち６号さんの書き込み (2005-11-16 13:54) より:

問題点のご指摘をお願いします m(_ _)m

[ メッセージ編集済み 編集者: でっち６号 編集日時 2005-11-16 14:05 ]


すいません、ざっとしか見ていないのですが…

参照元アドレス　＜　参照先アドレス

という前提が崩れると、だめな場合がないですか？
たとえば…アドレス０から始まる非循環リスト

　0 → 2 → 3 → 1 → Null

とか。
«前のページへ 1|2|3|4|5 次のページへ»

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