1

我一直在尝试使用 java 和 excel 获得四种不同功能的大 O。我不知道这些功能是什么，因为它们被隐藏了。我不确定这是否是正确的地方/论坛问。

我有使用一些java提供各种数据并将它们与步骤（1-n）一起放入excel的功能。然后，如果输出始终相同，我只使用 n 和它们所花费的时间的任意度量立即将它们放入图表中。例如，如果 n = 1 每次运行时总是等于 200。对于每次运行函数时都会发生变化的函数，我运行了 10 次函数并为每一步取平均值。

获得数据后，我为每个数据创建了一个图表，并在其上放置了一条趋势线。例如，我的 f(1) 最适合于多项式趋势线阶 2，我假设它是大 O? 的二次 (n2)。但我需要证明它是 n2，所以我做了 =Steps/LOG(N)，这使它最适合多项式趋势线阶 3，我假设它是 Cubic (n3)？（那正确吗？）

我真的不知道接下来要做什么来“证明”这个函数是二次函数或三次函数，或者如何证明它的最佳情况/最坏情况。

所以基本上我想弄清楚缺少的步骤是什么。

计算图趋势线？？？- 证明该函数具有大 O(?)

4

1 回答 1

0

当您说“如果 n=1 始终等于 200”时，这是否意味着如果 n=1 需要 200步才能运行？如果是这种情况，这个函数将是 200n 和这个 O(n)。

我认为要解决这个问题，您应该在不同的值上调用每个函数（我会从 10、20、30 ... 等开始）直到某个较高的数字。捕获这些值并在 Excel 中绘制它们。然后使用内置的趋势线功能。这应该可以让您粗略估计运行时间。从那里你应该能够得到Big-O。

于 2012-10-31T15:30:49.710 回答