big-o - アルゴリズム実行時間の定数部分を見つける

Question

O(n log n) で実行されるアルゴリズムの実装があります。n=10^7 の場合、アルゴリズムは 570 ミリ秒かかります。アルゴリズムの実行時間の定数部分 (C) を見つける方法を知っている人はいますか? アルゴリズムが任意の入力サイズに対して「必要な」時間を計算できるように、これが必要です。

Answer 1

正確に計算できるとは思いませんが、複雑さが確実にわかっている場合はO(n log n)、実行時間の見積もりとして単純な比率をお勧めします。

10^10 log 10^10   unknown run time
--------------- = ----------------
10^7 log 10^7           570 ms

この場合、約1428.6 * 570 ms =~ 814 sec.

これは数学的に正確ではありませんが、さまざまな定数を計算するために曲線に当てはめようとする複数のデータ ポイントがない場合は、開始するのに不合理な場所ではありません。