3

宿題の説明について質問があります。

http://www.cs.bilkent.edu.tr/~gunduz/teaching/cs201/cs201_homework3.pdf

配布資料を見るには、 http: //www.scribd.com/nanny24/d/36657378-Data-Structures-and-Algorithm-Analysis-in-C-Weiss の 25 ページにアクセスしてください。

以下は私がする必要があることですが、これが何を意味するのか理解できませんでした。アルゴリズム 1 の場合、実際の実行時間と (n^3 + 3*(n^2) + 2*n)/6、n=配列サイズを比較するという意味ですか? そうは思いませんが、それ以外は推測できませんでした。これが何なのか説明してもらえますか？

2- Plot the expected growth rates obtained from the theoretical analysis (as given for each solution) by 
using the same N values that you used in obtaining your results. Compare the expected growth rates 
and the obtained results, and discuss your observations in a paragraph.

編集2：

Algorithm 1:
    n           actual running time(ms)     (n^3 + 3*(n^2) + 2*n)/6 (I don't know whether the type is millisecond or not)
    100         1                       171700
    1000        851                     167167000

したがって、実際の実行時間と理論上の実行時間の間のこの大きな違いを考慮すると、インストラクターが意味することは、アルゴリズムの (n^3 + 3*(n^2) + 2*n)/6 である理論的な時間複雑度関数とは異なる場合があります。 1. これは関数です: http://www.diigo.com/item/image/2lxmz/m7y3?size=o

4

2 に答える 2

2

はい、講師は「予想成長率」とは、理論上の時間複雑度関数にnの値を代入した後の予測実行時間を意味します。

この使用法は標準的ですが、私があなたの場合はインストラクターに確認します.

于 2012-04-21T18:47:25.283 に答える
1

理論上の数は、おそらく操作または比較の数、または同様のものです。

成長率とは、値がどれだけ速く成長するかを意味していると思いますか? . nからになると、実際の測定係数 851 と比較して100、1000理論値は係数 だけ大きくなります。167167000/171700 = 973.6

于 2012-04-21T20:40:14.803 に答える