漸近的複雑さpython

Question

私は、このpythonコードの漸近的複雑さを見つけるタスクを持っています。

for i in range(x): 
    if i == 0: 
     for j in range(x): 
      for k in range(500): 
       print("A ") 

私が知っているところでは、500 * xであるはずです。最初のサイクルは1回しか行われないので（i == 0）、2回目はx回、3回目は500回なので、500 * xにする必要がありますか？しかし、これは正しい答えではありません。私を助けてくれますか？

Answer 1

漸近的複雑さは、可変因子が任意に大きくなるにつれて実行時間の増加を説明する。要約すると、加算または掛け算された定数は、すべてでカウントされません。これらの変数は変数で変更されないためです。

はい、500×x行が印刷されています。また、x-1回の非機能ループ反復もあります。あなたの合計時間は

（X-1）[ループオーバーヘッド] + X [ループオーバーヘッド] + 500 * X [ループオーバーヘッド+プリント 時間]

ようなものとして計算されますしかし、定数であるループオーバーヘッドは重要ではなく、複雑さの表現から脱落しています。同様に、500は倍率にすぎず、式からも除外されます。

複雑さはO（x）です。

Answer 2

また、xの行番号if i == 0をチェックする必要があるため、501 * xです。

他の答えによれば、通常、私たちは因子を含まない。しかし時には私たちはします。