1

配列内の偶数を配列の前に移動し、奇数を配列の後ろに移動しようとしています。問題は、線形アルゴリズムでこれを実行し、インプレースでこれを実行することを求めています。

私はこれを思いついた：

 def sort(a):
    for i in range(0,len(a)-1):
        if a[i]%2==0:
            a.insert(0,a.pop(i))
    return a

問題は、技術的にはa.insertはo（n）関数であるため、技術的にはこれは非線形アルゴリズムと見なされる（for i in range関数の一部を含める場合）と誰かが言ったことです。この質問をしたフォーラムは数ヶ月前なので、説明を求めることができませんでした。

基本的に、彼は「技術的に」と言ったと思います。これは、これが先頭に挿入されるため、配列内の別のN個の要素をチェックせず、したがって、O（n ^ 2）ではなくO（n）で実用的な目的で実行されるためです。 。これは正しい評価ですか？

また、フォーラムの誰かがa.append上記を変更し、奇数を探すように変更していました。誰も答えなかったので、私は疑問に思いました。a.appendは最後に移動するのでo（n）関数ではありませんか？o（1）ですか？

説明と説明をありがとう！

4

5 に答える 5

7

insertリストの0番目のインデックスでは、1つおきの要素をシフトする必要があります。これにより、O（N）操作になります。ただし、この操作を使用する場合dequeはO（1）です。

appendは、リストの最後にアイテムを追加するだけでシフトが行われないため、償却されたO（1）操作です。リストを大きくする必要がある場合があるため、必ずしもO（1）操作であるとは限りません。

于 2012-07-05T01:49:07.450 に答える
5

それは正しいです-Python標準リストの先頭への挿入はO（n）です。Pythonリストは配列として実装されているため、リストの先頭に何かを挿入するには、コンテンツ全体を1か所に移動する必要があります。一方、追加はシフトを必要としないため、O（1）で償却されます。

ただし、これa.pop(i)はO（n）操作でもあることに注意してください。これは、ポップされたアイテムの後のすべてを1つのスポットにシフトする必要があるためです。append()したがって、代わりに使用するようにコードを変更するだけinsert()では、線形アルゴリズムにはなりません。

線形時間アルゴリズムは使用しませんpop()が、代わりに要素を入れ替えるようなことを行うので、リストの残りの部分を変更する必要はありません。たとえば、次のことを考慮してください。

def even_to_front(a_list):
    next_even = 0
    for idx in xrange(len(a_list)):
        if not a_list[idx] % 2:
            # a_list[idx] is even, so swap it towards the front
            a_list[idx], a_list[next_even] = a_list[next_even], a_list[idx]
            next_even += 1
于 2012-07-05T01:49:31.540 に答える
2

追加/挿入またはデキューせずに実行する方法は次のとおりです

def sort(L):
    i, j = 0, len(L)-1
    while i<j:
        # point i to the next odd number from the start
        while i<j and not L[i]%2: i+=1
        # point j to the next even number from the end
        while i<j and L[j]%2: j-=1
        L[i],L[j] = L[j],L[i]
于 2012-07-05T02:38:04.617 に答える
1

この複雑さの表を確認してください

  • 挿入-O（n）
  • 追加-O（1）（リストが過剰に割り当てられている）
于 2012-07-05T01:49:22.410 に答える
0

popリストから要素を削除するたびに、リストの末尾部分をコピーして 1 つのインデックス上に移動し、削除された要素によって残された穴を埋める必要があります。これは、ポップされた要素とリストの末尾の間の距離に比例します。

insert要素をリストに入れるたびに、リストの末尾部分をコピーして 1 つのインデックスに移動し、新しい要素を挿入する場所を作成する必要があります。これは、要素を挿入する位置とリストの末尾の間の距離に比例します。

を使えばcollections.deque前後どちらにもO(1)時間的に追記・ポップできます。ただし、途中から要素を削除しても線形です（自分で作成する必要があると思います）。

于 2012-07-05T01:51:12.067 に答える