0

マージとヒープ ソートの両方をプログラムし、ランタイムの複雑さを計算しました。収集したデータ (c*(n*lg(n))) から、マージとヒープ ソートの定数 c を見つけたとします。以下は、要素数 (n) と実行時間 (秒) の 2 つのグラフ式 (Excel から) です。c 定数はどのように計算しますか? どんな助けでも大歓迎です！ありがとうございました。

ヒープ: y = 5E-12x2 + 2E-05x - 0.0561

マージ: y = 9E-10x2 - 9E-05x + 2.0958

4

1 に答える 1

0

あなたが与えた式は、定数a、b、およびcを持つ f( n ) = an 2 + bn + cの形式の多項式です。これらはあなたを助けるつもりはありません。

f( n ) = an lg( n ) + bn + cという形式の方程式をデータに適合させる必要があります。多項式ではなく、n lg( n ) 項を含む方程式です。その項の係数は、あなたが求めてきたものです。線形 ( b ) および定数 ( c ) の項は重要ではありません。n lg( n ) 項の定数は、それが最も速く成長するためです。

于 2012-10-17T02:08:05.343 に答える