0

我用append()Java 编写了一个函数，我需要通过 O(N) 和 Θ(N) 来分析它的运行时复杂性。

这是原始问题：

假设append()的运行时复杂度为t = O(N)，则意味着t也可以用 来表示t = C*N。（作为C一个常数）

因此(t / N) = C。

如果，例如，t = O(N^2)，那么(t / N^2) = C等等。

使用此方法查找append()运行时复杂性。

所以我append()为 3 个不同的 s 跑了 N 次N：1,000, 5,000, 10,000.

long start = System.currentTimeMillis();
for(i = 0; i < N; ++i) {
    append();
}
long end = long start = System.currentTimeMillis();

System.out.println(end - start);

我写下了end-start以毫秒为单位的运行时间。

现在，我如何使用这些信息来获得时间复杂度append()？

提前致谢！

4

2 回答 2

1

你误解了方法。N应该是字符串的长度，而不是函数调用的次数应该是

String str(n); // Or whatever how you create a string with n elements

long start = System.currentTimeMillis();
append();
long end = long start = System.currentTimeMillis();

System.out.println(end - start);

然后你运行它几个 Ns，并试图找出它的时间复杂度。尝试除以 t / N，然后除以 t / N^2，直到找到一个恒定的答案。

于 2013-11-01T10:44:03.587 回答
0

只有一个数据点，您无法确定函数的时间复杂度。凭经验确定时间复杂度的一个好方法是对多个不同大小的输入的操作进行计时，并查看操作运行时的相对增长率。例如，如果输入大小翻倍时运行时间大致翻倍，则时间复杂度为 O(n)。如果随着输入大小翻倍，运行时间大致翻了两番，则时间复杂度为 O(n 2 )。

您需要多个数据点的原因类似于您需要多个点来确定一条线的原因。仅给定一点，您无法判断斜率或截距是多少。在测量时间复杂度时，不能筛选出常数项和增长项的相对贡献。

希望这可以帮助！

于 2013-11-01T15:39:52.793 回答