程序运行时HW问题
程序运行时HW问题
提问于 2009-10-02 18:09:27
如果输入大小为500且程序为O(n lg(n))，则
algo需要.5 ms秒作为输入大小为100，运行多长时间？
我的书上说，当输入的大小加倍时，n lg(n)需要“略多于两倍的时间”。这对我没什么帮助。
我一直这么做的方法是求解常数乘数(书中没有提到这个问题，所以我不知道它是否有效)：
.5ms =c* 100 * lg(100) => c= .000753
所以
.000753 * 500 * lg(500) =3.37562 lg
这是计算运行时间的有效方法吗?是否有更好的方法来计算？
回答 2
Stack Overflow用户
发布于 2009-10-02 18:21:40
是。这正是它的工作原理。
当然，这会忽略任何可能的初始化开销，因为这不是在大o符号中指定的，但这与大多数算法无关。
Stack Overflow用户
发布于 2009-10-06 18:01:06
这不是完全正确的。托马斯说得对，这是有开销的，真正的等式更像是
runtime = inputSize * lg(inputSize) * singleInputProcessTime + overheadsingleInputProcessTime与机器操作有关，例如加载地址空间、算术或每次与输入交互时必须执行的任何操作。这通常有一个运行时，根据您的域从几个CPU周期到几秒钟或几分钟不等。重要的是要理解这个时间是大致恒定的，因此在足够大的输入大小下不会对整个运行时产生很大的影响。
开销是设置问题/解决方案的成本，例如将算法读入内存，在服务器/进程之间传播输入，或任何只需要执行一次或不依赖于输入大小的固定次数的操作。这个成本也是恒定的，根据解决问题的方法，可以从几个CPU周期到几分钟不等。
你已经知道的inputSize和n* lg(n)，但是关于你的家庭作业问题，只要你解释你是如何得到解决的，你就应该没事。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1511036
复制相关文章
相似问题
腾讯云开发者
