入力サイズが不明な場合のランタイムを推定する方法

Question

この本を使用して自分自身でアルゴリズム（最初の5つの章）を分析する方法を学習しています：Introduction of Algorithms。私は、次の単純なアルゴリズムを持っていると仮定し（私はそれを作った）：

for i <- 0 to 100 
    for j <- 1 to 2000 
    if (i*10 + j*20 = n) 
     c <- c+1 

さて、私は特定入力サイズのために、このアルゴリズムの実行中の時間を推定したい場合は、n= 500を言って、私が言うと思います：

最悪の場合の実行時間はT(n) = 100*2000*500 = 10 * 10^7です。しかし、入力サイズ（つまりn）を一般化したい場合は、これを行う方法がわかりません。親切に、誰かが私を啓発することができますか？

ありがとうございました

Answer 1

現在の実行時間が間違っています。 iとjの値は常にループするので、合計で100*2000回の繰り返しが必要です。これはあなたのn値から独立しています。しかし、未知数がそれぞれとjの値であると仮定すると、それぞれIとJと表示されます。アルゴリズムの実行時間がO(IJ)であると言えます。正しい軌道に乗っています。変数の定数を置き換えてください。