python - 特定の python アルゴリズムの時間計算量を見つける

Question

こんにちは、次のアルゴリズムの時間の複雑さを理解する必要があります。

def complex(n):
    l=[]
    i=1
    while i<n:
        l=list(range(i))
        i*=2

ループで int(log(n,2)) 回実行されることに気づきましたが、 range(i) を最終式に組み込むのに苦労しています。どんな助けでも感謝します。

Answer 1

list(range(i))これは、幾何学的に成長する i に基づいているため、見た目よりもトリッキーです。ただし、この問題を調べる簡単な方法があります。n に対して、合計でいくつの要素が作成されますか? n の便利な値、つまり 2 の累乗を仮定することで、問題を単純化できます。

それでも行き詰まっている場合は、小さく始めて上に進んでください。n = 1 の場合、合計でいくつの要素が作成されますか? 次に、n = 2、n = 4、n = 8 などに対して得られる答えを確認します。パターンはすぐに明らかになるはずです。