从运行时计算Big Theta？

Question

我有一个程序来计算运行时间以毫秒为单位的4个.txt文件。然后，我必须根据theta来计算加载的运行时间，并指定输入中指向的是n。但是，对于这个问题，我仍然不完全理解大的theta符号或渐近符号。任何人都可以给我几个指针？这些对于文件的运行时间：

文件的时间来加载

文件1个18000ms

文件2 48514ms

文件3 121473ms

文件4 622446ms

Answer 1

没有通用的办法从它的经验运行时导出程序运行时间的theta界限。可能有些输入是你没有看到的触发病态最坏情况的输入（例如，线性规划的单纯形算法在狭窄的输入类别下会恶化到指数最差情况），你无法知道你看到的是更长远的。

如果你想得到经验计算复杂性，一个合理的解决方案将采取您的数据，绘制在对数/对数轴上，并寻找最适合的线。这个原理的工作原理是，对数/对数图上的直线对应于多项式拟合，所以这将为您所拥有的数据找到最佳拟合多项式。只要您记得您的答案只会与您提供的数据一样好，那么这是解决复杂问题的好方法。