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=array size？我不这么认为，但我无法推断出其他任何东西。你能解释一下这是什么吗？

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从100到时，理论值按851 倍的实际测量因子1000增长。167167000/171700 = 973.6

于 2012-04-21T20:40:14.803 回答