计算给定递归函数的精确运行时(时间复杂度)

Question

考虑到此代码计算double x的幂

public static double F1 (double x, int k){
    if (k==1) { return x; } // O(1)
    return x * F1(x, k-1);  // O(k)
}

我的结论是

• if (k==1) { return x; }中的nr操作:2个操作、if-statement和return-statement。因此，T(1) = 2
• return x * F1(x, k-1);中操作的nr :4个操作，return-statement = 1，*-operator = 1，F1(x, k-1); = 2。
• 我们在x * F1(x, k-1),中有一个递归调用，所以x = 1。
• 在每个递归调用中，我们将问题减少1，所以y = k-1。所以方程的第二部分= T(k-1)

把这一切结合起来，我们就会得到：

4+ T(k-1)，T(1) =2

但是，我如何从这里开始找到确切的运行时呢？

我试图通过这问题来解释这个问题，但是它关注的是如何计算大O表示法，而不是精确的时间复杂度。我怎样才能找到确切的时间复杂性呢？

这里的答案应该是：

Exact: 4k-2 
Tilde: 4k 
Big-O: O(k)

但我不知道他们怎么做到的。

Answer 1

但是，我如何从这里开始找到确切的运行时呢？

你把你所做的一切都扔到垃圾堆里，然后用JMH来代替，稍后再看更多。

根据这种理论分析来确定精确的运行时间是完全不可能的。确切的运行时间取决于您的音乐播放器中播放的歌曲，您的操作系统是否忙于进行磁盘清理，是否向网络时间服务器发送ping，哪些页面恰好位于片上缓存中，您的代码在哪个CPU核心上运行，以及月亮的相位。

让我尽可能清楚地说:像4k - 2这样的东西是完全不相关和被误导的--这不是计算机的工作方式。不能说具有“精确运行时”4k - 2的算法比6k + 2算法更快。它同样有可能变慢:它拥有零的预测能力。这是一个完全没有意义的“计算”。没什么意义。大-O表示法存在的原因是:这确实意味着不管硬件的变幻莫测:给定两个算法，其中一个比另一个有“更好的”大O表示法，那么就会有一些输入大小，这样更好的算法就会更快，而不管硬件方面的问题。它可能是一个非常大的数字，而大-O没有做任何事情来告诉你在什么数字发生这种情况。

大O表示法的意义在于，它用数学上的确定性来说明，如果你用非常宽泛的笔画改变算法的输入大小，最终会发生什么。这就是为什么在显示大-O符号时，删除所有常量和所有内容，但最大的因素除外。

取一个图形；在X轴上，有‘输入大小’，这是O(k)中的'k‘。在Y轴上，有执行时间(或者如果你愿意的话，最多)。内存负载)。然后，设置一些输入大小，并运行您的算法几次。对结果进行平均，并在该图形上放置一个点。例如，如果您在k=5的输入上运行算法，并且平均花费27 on，那么在x=5，y=27上放置一个点。

继续走。很多点。最终，这些点形成了一个图形。图将在x=0点附近，到处都是。就像一个醉汉喜欢随意性，就像把飞镖扔到木板上一样。

但是，最终(当“最终”起作用是无法确定的，因为它同样依赖于如此多的操作系统，不要费心去预测这样的事情)，它将开始看起来像一个可识别的形状。我们用简单的公式来定义这些形状。例如，如果它最终(向右足够远)合并成类似于图形y=x^2的东西，那么我们称之为O(x^2)。

现在，y=5x^2看起来非常像y=x^2。在这个问题上，y=158*x^2 + 25000x + 2134931239，如果你在这条曲线上向右看的足够远，看起来就像y=x^2。因此，为什么O(158x^2+20x)完全没有注意到这一点，因此是不正确的。O的意义仅仅是告诉你它会是什么样子的‘足够远的右边’。

这就给我们留下了两个有用的性能指标：

1. O(k)符号您在这里正确地确定了这一点:该算法有一个O(k)运行时。
2. 一份时间报告。没有意义试图通过查看代码来解决这个问题，您需要运行代码。为了确保hotspot优化不会完全消除代码，多次重复运行以获得良好的平均值，并确保我们通过JVM的JIT步骤。您可以使用JMH来完成这一任务，并注意到JMH的结果当然取决于运行它的硬件，这是因为根据硬件的不同，程序可能具有截然不同的性能特征。

Answer 2

对于执行的第一个k-1步骤：

1. 比较k==1
2. 减法k-1
3. 产品x * ...
4. return指令

在最后一步执行：

1. 比较k==1
2. return指令

因此，您有4*(k-1)+2 = 4k-2的总体说明。

编辑：正如@rzwitserloot正确指出的那样，搜索的数量不是很大，但这取决于代码是如何编译和执行的。上面我试着用“精确的时间复杂性”来理解你的老师的意思。