アルゴリズムの複雑さを判断する

Question

私はこの質問を受けました。以下のアルゴリズムの説明を読んでください。各アルゴリズムについて、nのリストの最悪の場合の時間パフォーマンスを最もよく表す次の複雑度クラスのどれを説明します。

Lのi番目の要素がLの（i + 1）番目の要素より小さい場合、Trueを返します。浮動小数点数のリストLおよび整数0 < = i < len（L） - 1各アルゴリズムの実装は、サイズ2nのリストとサイズnのリストのリストで実行されたときに出現するはずです。

私はこれについてO（1）であると推測しました。サイズ2nのリストとサイズのリストのリストを実行したときの実装の動作を理解していません。

Answer 1

これはO（1）の複雑さを想定しています。

O（1）アルゴリズムは、データの任意のサイズの上に1つの一定の時間を要すること、サイズnのリストに対する サイズ2nのリスト上で実行したとき、私は は、実装の振る舞いを理解していません。配列の要素へのアクセスは典型的な例です。

Pythonでは、リストは配列データ構造体ではありません。ディクショナリにはハッシュテーブルが使用されているため、おそらくO（1）があります。