1

おそらくコンパイラの理解が不足しているために、私はいつもこれについて少し混乱してきました。しかし、例としてPythonを使用してみましょう。numlistと呼ばれる数値の大きなリストがあり、重複を取り除きたい場合は、リストで集合演算子（set（numlist）の例）を使用できます。その見返りに、私たちは私たちの番号のセットを持っているでしょう。私の知る限り、この操作はO（n）時間で実行されます。この操作を処理するために独自のアルゴリズムを作成する場合でも、私がこれまでに期待できる最高のものはO（n ^ 2）です。

私が得られないのは、set（）のような内部操作が言語アルゴリズムの外部よりもはるかに高速になることを可能にするものです。まだチェックが必要ですね。

4

6 に答える 6

3

Θ(n)これは、ハッシュ テーブルを使用して平均時間で実行できます。ハッシュ テーブルへの参照と挿入はΘ(1)平均的です。したがって、nアイテムを実行し、それぞれがハッシュ テーブルに既に存在するかどうか、アイテムを挿入していないかどうかを確認するだけです。

私が得られないのは、 set() のような内部操作が言語アルゴリズムの外部よりもはるかに高速になる理由です。チェックはまだ行う必要がありますね。

アルゴリズムの漸近的な複雑さは、言語の実装者によって実装された場合と、言語のユーザーによって実装された場合では変わりません。両方がランダムアクセスメモリモデルを備えたチューリング完全言語で実装されている限り、それらは同じ機能を持ち、それぞれに実装されたアルゴリズムは同じ漸近的複雑さを持ちます。アルゴリズムが理論的O(f(n))には、アセンブリ言語、C#、または Python で実装されているかどうかは問題ではありませんO(f(n))。

于 2010-02-05T04:05:39.970 に答える
1

アルゴリズムの複雑さの限界は、それが「内部的に」実装されているか「外部的に」実装されているかとは完全に無関係です。

于 2010-02-05T03:46:53.847 に答える
1

リストを取り、それをセットに変換するのset()はO（n）です。

これは、setがハッシュセットとして実装されているためです。つまり、セットに何かが含まれているかどうかを確認したり、セットに何かを追加したりするには、一定時間のO（1）しかかかりません。したがって、イテラブル（たとえばリストなど）からセットを作成するには、空のセットから始めて、イテラブルの要素を1つずつ追加します。n個の要素があり、各挿入にはO（1）がかかるため、反復可能オブジェクトをセットに変換する合計時間はO（n）です。

ハッシュ実装がどのように機能するかを理解するには、ハッシュテーブルに関するウィキペディアの記事を参照してください。

于 2010-02-05T03:51:36.353 に答える
1

基本的に次のように、任意の言語の O(n) でこれを行うことができます。

# Get min and max values O(n).

min = oldList[0]
max = oldList[0]
for i = 1 to oldList.size() - 1:
    if oldList[i] < min:
        min = oldList[i]
    if oldList[i] > max:
        max = oldList[i]

# Initialise boolean list O(n)

isInList = new boolean[max - min + 1]
for i = min to max:
    isInList[i] = false

# Change booleans for values in old list O(n)

for i = 0 to oldList.size() - 1:
    isInList[oldList[i] - min] = true

# Create new list from booleans O(n) (or O(1) based on integer range).

newList = []
for i = min to max:
    if isInList[i - min]:
        newList.append (i)

appendここでは、実装者が脳死していない限り、O(1) 操作であると想定しています。したがって、各 O(n) ごとに k ステップを使用しても、O(n) 操作が必要です。

手順がコードで明示的に実行されるか、言語のカバーの下で実行されるかは関係ありません。それ以外の場合は、Cqsortは 1 つの操作であり、O(1) ソート ルーチンの聖杯を手に入れたと主張できます :-)

多くの人が発見したように、多くの場合、空間の複雑さと時間の複雑さをトレードオフできます。たとえば、上記はisInListandnewList変数の導入が許可されているためにのみ機能します。これが許可されていない場合、次善の策は、リストをソートし（おそらくO（n log n）よりも優れていない）、その後にO（n）（私が思うに）操作を行って重複を削除することです。

極端な例として、約 40 億バイトを割り当てることができれば、同じ余分なスペースの方法を使用して、O(n) 時間で任意の数の 32 ビット整数 (それぞれが 255 個以下の重複しか持たないなど) をソートできます。カウントを保存します。

すべてのカウントをゼロに初期化し、リスト内の各位置を実行して、その位置の数に基づいてカウントをインクリメントするだけです。それが O(n) です。

次に、リストの先頭からカウント配列を実行し、その数の正しい値をリストに配置します。これは O(1) で、1 はもちろん約 40 億ですが、それでも時間は一定です :-)

これも O(1) 空間の複雑さですが、非常に大きな「1」です。通常、トレードオフはそれほど深刻ではありません。

于 2010-02-05T04:23:19.067 に答える
0

手元では、O（n）でこれを行う方法を考えることはできませんが、ここにクールなことがあります。

n ^ 2とnの違いは非常に大きいので、それを実装することとpythonを実装することの違いは、それを実装するために使用されるアルゴリズムと比較してわずかです。n ^ 2がCにあり、O（n）がpythonにある場合でも、n ^ 2は常にO（n）よりも劣ります。この種の違いは、低水準言語で書いているわけではないという事実から来ると決して考えるべきではありません。

とはいえ、独自に実装する場合は、並べ替えを行ってから重複を削除できます。ソートはn*ln（n）で、O（n）の重複を削除します。

于 2010-02-05T03:51:05.553 に答える
0

ここには 2 つの問題があります。

時間計算量 (ビッグ O 表記で表されます) は、特定のセット サイズでアルゴリズムを実行するのにかかる時間の正式な尺度です。絶対的な速度よりも、アルゴリズムがどれだけうまくスケーリングするかが重要です。

アルゴリズムの実際の速度 (たとえば、ミリ秒単位) は、時間の複雑さに定数を掛けたものです (理想的な世界では)。

2 人で O(log(n)*n) の複雑さで同じ重複除去アルゴリズムを実装できますが、一方が Python で記述し、もう一方が最適化された C で記述した場合、C プログラムの方が高速になります。

于 2010-02-05T04:23:08.180 に答える