分析函数运行时复杂度

我已经写了一个函数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()运行时coplexity。

于是我就append() N次3个不同N S：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()时间coplexity？

在此先感谢！

来源

2013-11-01 Billie

你已经有了时间复杂性，这是O（N）的事情。你问的是不变的，这是一个模糊的计算复杂性**最好的** - 你为什么这样做？如果您想比较真实世界的性能，可以跳过该部分并直接比较测量的时间。这就是所谓的基准。 – delnan

您误解了方法。 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，并试图找出它是时间coplexity。尝试划分t/N，然后t/N^2，直到你找到一个恒定的答案。

来源

2013-11-01 10:44:03 LeeNeverGup

只有一个数据点，您无法确定函数的时间复杂度。以经验方式确定时间复杂度的一个好方法是对多个不同大小的输入进行操作，并查看操作运行时的相对增长率。例如，如果随着输入大小加倍，运行时大致加倍，则时间复杂度为O（n）。如果随着输入大小加倍，运行时间大约增加四倍，则时间复杂度为O（n ）。

Tje您需要几个数据点的原因类似于为什么您需要几个点来确定一条线。只给出一点，你不能说出斜率或截距是什么。在衡量时间兼容性时，您不能筛选竞争项和增长项的相对贡献。

希望这会有所帮助！

来源

2013-11-01 15:39:52 templatetypedef

分析函数运行时复杂度

回答

相关问题