performance - 複雑な形式で表されたアルゴリズムの実行時間の比較

Question

異なるアルゴリズムの実行時間を比較する方法を知っています。

明らかな場合もあれば、単純化が必要な場合もあり、ロピタルの法則を分割して使用して、定数または 0 に収束するかどうかを確認することもあります。

しかし、機能が複雑な形である場合、どのように機能を比較しますか?

たとえば、どのように比較しますか

そしてn？

もちろん、厳密な証明が必要です。

Answer 1

この例では、最初の単純化はsqrt(2)-0.4電力を削除することです。その力は非常に近いので1、ほとんど違いはありません。比較にこの区別が必要な場合はお詫び申し上げます。これにはおそらく累乗の法則があるのでしょうが、私は自分の数学をあまりよく覚えていません。

次に、ログ ルールを使用して、ログ₉₆ nを因数分解します。

これに相当するのはlog ₂ n / log ₂ 96です。これで、前者の2乗ができました。 log ₂ 96は単なる定数 (約 6.585) です。これを除外することも (n増加すると重要でなくなるため)、そのままにして別のログ ルールを使用することもできます。それを残しましょう：

log ₂ n / log ₂ 96はlog ₂ n ^{(log ₂ 96) -1になります。}

全体がn ^{(log ₂ 96)-1}に単純化されます。または、さらに単純化すると、2 ^ log ₂ nになりますが、これは単なるnです。

nと比較したかったので、最初の結果の方が関連性が高いように見えます。これは約0.15nです。

Answer 2

それはそれぞれの問題に特有のものです。この場合、n = 96^k および 96 = 2^m とします。

n vs 式は次のように書き直すことができます。

2^(m*k) vs 2^(k ^(sqrt(2) - 0.4))

2, m, k, sqrt(k) - 0.4 はどちらも > 0 なので、比較は次のようになります。

(m * k) vs k ^(sqrt(2) - 0.4)

また

m vs k ^(sqrt(2) - 1.4) 

ただし、m = log 96 を基数 2 に固定 (6.585) し、k は無制限です。

したがって、式 (RHS) は大きくなります。