如果复杂性是O(nlog2(n))......如何证明数据的执行时间，比如10e7我们知道数据的10e5执行时间是 0.1 秒？
anon
问问题
86 次
1 回答
1
简而言之：据我所知，您无法以这种方式证明这一点。
更详细地说：
关于复杂性的事情是它们以大 O 表示法报告，其中任何常量和低阶项都被丢弃。例如; 问题的复杂性O(nlog2(n))，但这可能是 的简化形式k1 * n * log(k2 * log(k3 * n + c3) + c2) + c1。
这些常量涵盖了诸如初始化任务之类的事情，无论样本数量如何，初始化任务都需要花费相同的时间，执行该log2(n)位所需的比例时间（其中每一个都可能比该n位长 10^6 倍）等等。
除了常量之外，您还有可变因素，例如执行算法的硬件、系统上的任何额外负载等。
为了将其用作估计执行时间的基础，您需要有足够的关于问题大小的执行时间样本来估计常量和变量因子。
出于实际目的，可以为一组足够大的问题规模收集多个执行时间样本，然后根据您的复杂性公式使用合适的函数拟合数据。
在证明执行时间方面......并不是真正可行的，你能希望的最好的就是一个最合适的模型和一个显着的 p 值。
当然，如果你想要的只是一个粗略的猜测，你总是可以尝试假设所有的常量和变量都是 1 或 0 并插入你拥有的数字：(0.1s / (10^5 * log2(10^5))) * (10^7 * log2(10^7)) = 11 ish
于 2015-01-19T22:52:00.227 回答