python内蔵メソッドの時間的複雑さ
Pythonにおけるいくつかの方法の時間的複雑さ(あるいは「大欧」「Big O」)である.この時間的複雑度の計算は、現在のCPythonに基づいて実現される.他のPythonの実装(古いバージョンや開発中のCPython実装を含む)は、パフォーマンスの表現にわずかな違いがあるかもしれませんが、一般的にはO(log n)項目を超えません.
注意:ここで、「n」はコンテナ内の要素の数、「k」はパラメータの値、またはパラメータの数を表します.
List(リスト)
リストは配列(Array)で実現される.最大のオーバーヘッドは、現在の割り当てサイズを超える増加で発生します.この場合、すべての要素が移動する必要があります.または、開始位置付近で要素を挿入または削除する場合は、その位置の後ろにあるすべての要素を移動する必要があります.1つのキューの両端で削除する必要がある場合は、
操作
へいきんじょうたい
最悪の場合
コピー
O(n)
O(n)
append[注1]
O(1)
O(1)
挿入
O(n)
O(n)
要素をとる
O(1)
O(1)
要素の変更
O(1)
O(1)
要素の削除
O(n)
O(n)
遍歴する
O(n)
O(n)
スライス
O(k)
O(k)
スライスの削除
O(n)
O(n)
スライスの変更
O(k+n)
O(k+n)
extend[注1]
O(k)
O(k)
ツールバーの
O(nlogn)
O(nlogn)
リスト乗算
O(nk)
O(nk)
x in s
O(n)
max(s) min(s)
O(n)
len
O(1)
O(1)
collections.deque(双方向キュー)
deque(double-ended queue、双方向キュー)は、双方向チェーンテーブルとして実装される(Well,a list of arrays rather than objects,for greater efficiency).双方向キューの両端は可能ですが、検索キューの間の要素が遅いため、要素の削除が遅くなります.
操作
へいきんじょうたい
最悪の場合
コピー
O(n)
O(n)
append
O(1)
O(1)
append left
O(1)
O(1)
pop
O(1)
O(1)
pop left
O(1)
O(1)
extend
O(k)
O(k)
extend left
O(k)
O(k)
rotate
O(k)
O(k)
remove
O(n)
O(n)
set(集合)
リストされていない操作はdictを参照できます.両者の実装は非常に似ています.
操作
へいきんじょうたい
最悪の場合
x in s
O(1)
O(n)
並列s|t
O(len(s)+len(t))
交差s&t
O(min(len(s)),len(t))
O(len(s)*len(t))
差セットs-t
O(len(s))
s.difference_update(t)
O(len(s))
O(len(s)*len(t))
対称差セットs^t
O(len(t))
O(len(t)*len(s))
s.symmetric_difference_update(t)
集合のs−t演算では,tも必ず集合であることは要求されない.tが遍歴可能なオブジェクトであればソースコードから分かるように、求差セット(
集合のs−t演算では,tも必ず集合であることは要求されない.tが遍歴可能なオブジェクトであればよい
dict(辞書)
次の辞書の平均は、次の仮定に基づいています.1.オブジェクトのハッシュ関数は、競合しないようにロッドを引っ張るのに十分です.2.辞書のキーは、可能なすべてのキーのセットからランダムに選択されます.
コツ:文字列のみを辞書のキーとして使用します.アルゴリズムの時間的複雑さには影響しませんが、定数項に顕著な影響を与え、プログラムがどれだけ速く走るかを決定します.
操作
へいきんじょうたい
最悪の場合
コピー[注2]
O(n)
O(n)
要素をとる
O(1)
O(n)
要素の変更[注1]
O(1)
O(n)
要素の削除
O(1)
O(n)
遍歴する
O(n)
O(n)
注意:
[1] = These operations rely on the “Amortized” part of “Amortized Worst Case”. Individual actions may take surprisingly long, depending on the history of the Container.
[2] = For these operations, the worst case n is the maximum size the container ever achieved, rather than just the current size. For example, if N objects are added to a dictionary, then N-1 are deleted, the dictionary will still be sized for N objects (at least) until another insertion is made.
この記事は以下のとおりです.https://www.cnblogs.com/harvey888/p/6659061.html
注意:ここで、「n」はコンテナ内の要素の数、「k」はパラメータの値、またはパラメータの数を表します.
List(リスト)
リストは配列(Array)で実現される.最大のオーバーヘッドは、現在の割り当てサイズを超える増加で発生します.この場合、すべての要素が移動する必要があります.または、開始位置付近で要素を挿入または削除する場合は、その位置の後ろにあるすべての要素を移動する必要があります.1つのキューの両端で削除する必要がある場合は、
collections.deque(双方向キュー)を使用します.操作
へいきんじょうたい
最悪の場合
コピー
O(n)
O(n)
append[注1]
O(1)
O(1)
挿入
O(n)
O(n)
要素をとる
O(1)
O(1)
要素の変更
O(1)
O(1)
要素の削除
O(n)
O(n)
遍歴する
O(n)
O(n)
スライス
O(k)
O(k)
スライスの削除
O(n)
O(n)
スライスの変更
O(k+n)
O(k+n)
extend[注1]
O(k)
O(k)
ツールバーの
O(nlogn)
O(nlogn)
リスト乗算
O(nk)
O(nk)
x in s
O(n)
max(s) min(s)
O(n)
len
O(1)
O(1)
collections.deque(双方向キュー)
deque(double-ended queue、双方向キュー)は、双方向チェーンテーブルとして実装される(Well,a list of arrays rather than objects,for greater efficiency).双方向キューの両端は可能ですが、検索キューの間の要素が遅いため、要素の削除が遅くなります.
操作
へいきんじょうたい
最悪の場合
コピー
O(n)
O(n)
append
O(1)
O(1)
append left
O(1)
O(1)
pop
O(1)
O(1)
pop left
O(1)
O(1)
extend
O(k)
O(k)
extend left
O(k)
O(k)
rotate
O(k)
O(k)
remove
O(n)
O(n)
set(集合)
リストされていない操作はdictを参照できます.両者の実装は非常に似ています.
操作
へいきんじょうたい
最悪の場合
x in s
O(1)
O(n)
並列s|t
O(len(s)+len(t))
交差s&t
O(min(len(s)),len(t))
O(len(s)*len(t))
差セットs-t
O(len(s))
s.difference_update(t)
O(len(s))
O(len(s)*len(t))
対称差セットs^t
O(len(t))
O(len(t)*len(s))
s.symmetric_difference_update(t)
集合のs−t演算では,tも必ず集合であることは要求されない.tが遍歴可能なオブジェクトであればソースコードから分かるように、求差セット(
s-t、またはs.difference(t))演算と、差セット(s.difference_uptate(t))演算に更新される時間の複雑さは異なる!前者はsにあるがtにない要素を新しい集合に追加するので,時間複雑度はO(len(s))である.後者は、t中の要素をsから除去するので、時間的複雑度はO(len(t))である.したがって,2つの集合の大きさや新しい集合が必要かどうかに応じて適切な方法を選択することに注意して使用する.集合のs−t演算では,tも必ず集合であることは要求されない.tが遍歴可能なオブジェクトであればよい
dict(辞書)
次の辞書の平均は、次の仮定に基づいています.1.オブジェクトのハッシュ関数は、競合しないようにロッドを引っ張るのに十分です.2.辞書のキーは、可能なすべてのキーのセットからランダムに選択されます.
コツ:文字列のみを辞書のキーとして使用します.アルゴリズムの時間的複雑さには影響しませんが、定数項に顕著な影響を与え、プログラムがどれだけ速く走るかを決定します.
操作
へいきんじょうたい
最悪の場合
コピー[注2]
O(n)
O(n)
要素をとる
O(1)
O(n)
要素の変更[注1]
O(1)
O(n)
要素の削除
O(1)
O(n)
遍歴する
O(n)
O(n)
注意:
[1] = These operations rely on the “Amortized” part of “Amortized Worst Case”. Individual actions may take surprisingly long, depending on the history of the Container.
[2] = For these operations, the worst case n is the maximum size the container ever achieved, rather than just the current size. For example, if N objects are added to a dictionary, then N-1 are deleted, the dictionary will still be sized for N objects (at least) until another insertion is made.
この記事は以下のとおりです.https://www.cnblogs.com/harvey888/p/6659061.html