この質問は、this answerのコメントの議論から生じました。リスト内で順序が間違っている要素をすべて選択するにはどうすればよいですか？
最初に、不注意なものを定義することは非常に難しいとしましょう。 Pavel Shvedの例を挙げると、[1,5,10,2,3,4,5,6,7,8,9,10,11]のリストでは、5と10の値を「はっきり」見ることができます（指標1 2）順不同です。しかし、ソートされたリスト不変のものを単にチェックする単純なアルゴリズムは、それらを指摘しません。 a[i-1]<=a[i] for all 0<i<=Nをチェック
は、（2）指標3で要素を生じます。
チェックa[j]<=a[i] for all 0<=i<=N and 0<=j<=iは、インデックス3から12のすべての要素を返します。
私の質問は、「正しい答え」（すなわちインデックス1と2）を生成するこの問題を解決するアルゴリズムと考えることができますか？もしそうなら、それは何時とメモリの複雑さの下で実行されますか？
これに最も適した方法は、最初にlongest increasing subsequenceを見つけて、そのシーケンスに含まれていないすべての要素を順不同とみなすことです。リンクされたページで提供されるアルゴリズムは、O(n log n)時間で実行され、O(n)スペース（リスト自体のアルゴリズムに加えて）を使用します。
このような最長の増加部分列は1から11までのシーケンスが含まれていないだろうので、間違いなく、あなたの例の場合に正しい答えをもたらすであろうアプローチ余分5とアルゴリズムが知っておくべきどのよう
を指摘しました。最初の例では動作しますが、この例は[1、10、2、3、4、6、5]です。 10と6は順不同ですが、1と5はそうではありません。Botz3000が指摘しているように、順不同を明確に定義することができないので、私はそれを考えると、疑問点が多いようです。 。 –
ああ、待って！私はリンクをチェックしなかった。なぜなら、最も長くなるサブシーケンスが何を意味するのか分かっているからだと思ったからだ。それから、私はこの「この部分列は必ずしも連続しているわけではありません」と読んでいます。さて、私はそれが解決策かもしれないと思います。 –
[1、2、3、4、6、5]の意味は、あいまいであることを意味します - 6は故障している可能性があります。左または右の単一の場所は、リストのその部分を「順序付け」するだろう。言い換えれば、「5があまりにも遠い」または「6があまりにも遠い」と言うことができ、どちらも本質的に「無秩序度」の点で同等であると言えるでしょう。 – Amber
10.どの要素あなたを考慮していない？
ルールが「list [i + 1]は常にlist [i] + 1でなければならない」場合は、もちろん、1の後に次の要素が2であることを暗記するのは簡単です間に、など。しかし、どの要素を「順不同」とみなすべきかを決定するためのアルゴリズムの正確なルールが必要です。
Davが言ったように、longest increasing subsequenceはおそらくあなたができる最高のものです。
これは私の頭の上から外れているので、それはおそらくPではありません。正しい： 少なくとも1回は各数字を読む必要があるため、この問題の明らかな下限はO（n） 。しかし、O（n）時間に実行されたアルゴリズムがあったとします。次に、順序のずれた要素を線形時間で順番に挿入することができますが、最適な比較ソートアルゴリズムはO（nLogn）の下限を持つので、矛盾です。 （そうでなければ、大量のメモリを使用するか、ソートされる数値のサイズを悪用するバケットまたは基数ソートのような非比較ソートメソッドがあります...）
修正。 Nの因子は、リスト内の各要素を処理するために必要であり（必要性）、その要素がどこに属するかを決定するためにlog Nの因子が必要とされる。したがって、ソートされた結果を保証する任意のアルゴリズムは、O（N log N）の下限を有する。 – Amber
+1元の質問から全く新しい質問 –