2

この回答へのコメントでは、単純にリンクされたリストの反転は O(n) 時間ではなく、O(nlog(n)) でしか実行できないという考えが提起されています。

これは間違いなく間違っています。O(n) 反転は問題ではありません。リストをたどってポインタを変更するだけです。3 つの一時ポインターが必要です。これは、一定の余分なメモリです。

O(nlog(n)) は O(n) よりも悪い (遅い) ことを完全に理解しています。

しかし、好奇心から-単純にリンクされたリストを反転するための O(nlog(n)) アルゴリズムは何でしょうか? 一定の余分なメモリを持つアルゴリズムが望ましいです。

4

6 に答える 6

11

私はあなたが混乱していると思います。あなたは、実際には O(n) よりも悪い O(n log(n)) と言っています。おそらくO（log n）のことですか？もしそうなら、答えはノーです。O(log n) で連結リストを反転することはできません。O(n) は自明です (そして明らかな解決策です)。O(n log(n)) はあまり意味がありません。

編集： O（n log（n））を意味します。答えはイエスです。どのように？簡単。リストを並べ替えます。

  1. リストの長さを数えます。コスト: O(n);
  2. 同じサイズの配列を作成します。
  3. リンク リストの要素をランダムな順序で配列にコピーし、元の順序を要素の一部として配置します。例: [A,B,C] -> [(B,2),(C,3),(A,1)]. コスト: O(n);
  4. [(C,3),(B,2),(A,1)] のように元の順序を逆にして、効率的な並べ替え (クイック ソートなど) を使用して配列を並べ替えます。コスト: O(n log(n));
  5. 逆配列から連結リストを作成します。コスト: O(n)。

総コスト: O(n log(n))

すべての中間ステップにもかかわらず、ソートは最もコストのかかる操作です。O(n) 個のその他のステップは一定であるため (つまり、ステップ数は n の因数ではない)、総コストは O(n log(n)) です。

編集 2:私はもともとリスト項目をランダムな順序で並べていませんでしたが、既に並べ替えられたリストの効率的な並べ替えは、逆にしていても O(n log(n)) 未満であると主張できることに気付きました。今、私はそれが事実であると完全に確信しているわけではありませんが、上記の改訂により、その潜在的な批判が取り除かれています.

はい、これは病理学的な質問 (および回答) です。もちろん、O(n) で実行できます。

于 2009-07-21T09:35:34.423 に答える
7

すべての O(n) アルゴリズムは O(n log n) でもあるため、答えはイエスです。

于 2009-07-21T09:44:21.990 に答える
1

良い...

入力が 2 つのノードだけの場合、リンク リストの 2 つの半分でそれ自体を呼び出すことにより、リンク リストを受け入れて反転する再帰を使用できます。

これは非常に非効率的ですが、O(nlog(n)) だと思います...

疑似コードで次のようなもの ( lenO(n) でリストの長さを返すsub_list(list, start_id, end_id)関数と、O(N) で start_id で始まり end_id で終わるリストのサブセットを返す関数があると仮定します):

function invert(list)

    if len(list) == 1 return list

    if len(list) == 2:
        new_list = list.next
        new_list.next = list
        return new_list

    middle_of_list = len(list) / 2  <-- integer division

    first_half = invert ( sub_list(list, 1, middle_of_list) )
    second_half = invert ( sub_list(list, middle_of_list+2, len(list) )

    first_half.next = second_half

    return first_half
于 2009-07-21T09:42:27.640 に答える
1

ばかげた考えですが、O(n log n) であり、O(n) ではありません

  • リストの各アイテムに一意の ID を割り当てます。各後続の ID は、アイテムの ID (O(n))よりも大きくする必要があります
  • 任意の比較ベースのソート アルゴリズム(O(n log n))を使用して、id をキーとしてアイテムを昇順でソートします。
  • アイテムをソートすることによって与えられた順序を使用して、新しいリストを作成します(O(n))
于 2009-07-21T09:44:24.173 に答える
0

あなたがペダンティックであれば、このアルゴリズムは O(n log n) です。これは、ポインターのサイズが少なくとも log n であり、n 回割り当てられる必要があるためです。

しかし、実際にはマシンのワード サイズは固定されているため、通常、これは考慮されません。

于 2009-07-21T10:35:39.217 に答える