python リスト→セットにする際の計算量のオーダー

Question

pythonで、あるリストをset()を用いてセットに変換する際の計算量のオーダーを教えていただきたいです。

Answer 1

• リストをセットに変換する際の計算量は何に依存するのでしょうか。

非常に多くのものに依存します。

リストの各要素の型、リストの各要素が他のどこから参照されているか、リストの各要素がコンテナオブジェクトの場合にはその中身、動作しているOS、動作しているPythonの種類、その瞬間のPython処理系のメモリの使用状況などが入っていることは間違いありませんが、他にもあるでしょう。

PythonがCPythonの場合でしたらソースが公開されていますので、詳しいことを調べたければ、cpython/Objects/setobject.cの1945行目あたりから順に辿って読むのでしょうが、非常に大変です。

Comments

[DUM1106]

非常に詳しく教えていただきありがとうございます。リストからセットにする際の計算量のオーダーも教えていただけると幸いです。私の質問が曖昧でした。すみません。

[ppaul]

リストの各要素がコンテナオブジェクトの場合にはその中身が問題になるので、理論的には長さ１のリストであったも無限大の時間がかかる可能性があります。実際にはメモリの制約があるのでそういうことは起こりません。
「AtCoder TLEの原因」で現れるようなリストであれば、リストの長さにほぼ比例します。しかし、「AtCoder TLEの原因」が遅いのは、append、set変換、popleftという、そこそこのコストの処理を大量に行っていることなので、計算量のオーダーではなく比例定数の方が問題なのです。
オーダーと比例定数の違いがわからないのであれば、ネットで検索して勉強することをお勧めします。

[DUM1106]

ご回答ありがとうございました。まだご指摘の部分の理解が不十分だと分かったので、今後勉強したいと思います。