c++ - 算法分析——预期增长率

Question

我有一个关于澄清我的家庭作业的问题。

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

Answer 1

是的，您的讲师所说的“预期增长率”是指在理论时间复杂度函数中插入 n 值后的预测运行时间。

虽然这种用法是标准的，但如果我是你，我仍然会与讲师核实。