java - 分析短算法的运行时间

Question

我得到了以下代码:

public class alg 
{
    public static int hmm (int x)
    {
        if (x == 1)
        {
            return 2;
        }
        return 2*x + hmm(x-1);
    }

    public static void main (String[] args)
    {
        int x = Integer.parseInt(args[0]);
        System.out.println(hmm(x));
    }
}

那么第一个问题是，这个算法算什么？我刚刚在 eclipse 中输入并运行了它所以我可以更好地看到它的作用(之前是伪代码，我不能在这里输入它所以我输入了代码)。我已经意识到该算法执行以下操作:它将接受输入并将其乘以其以下数字。举个例子:

input = 3, output = 12 because 3*4 = 12.  
Or Input = 6, output 42 because 6*7 = 42.

好了，下一个问题是我的问题。我被要求分析这个算法的运行时间，但我不知道从哪里开始。我会说，一开始，当我们定义 x 时，我们已经得到了 time = 1我相信 if 循环也会给出 time = 1。最后一部分，return 2x + alg(x-1) 应该给出“something^x”或者..？所以最后我们得到了类似 "something^x"+ 2 的东西，我怀疑那是对的:/

编辑，也设法输入伪代码:)

Input: Integer x with x > 1
if x = 1 then
  return 2;
end if
return 2x + hmm(x-1);

Answer 1

遇到问题时，请尝试使用(小)数字遍历代码。

这算什么？

我们以hmm(3)为例:

1. 3 != 1，所以我们计算 2 * 3 + hmm(3-1)。向下递归级别。
2. 2 != 1，所以我们计算 2 * 2 + hmm(2-1)。向下递归级别。
3. 1 == 1，所以我们返回 2。不再有递归，因此 hmm(2-1) == hmm(1) == 2。
4. 返回一级递归，我们得到 2 * 2 + hmm(1) = 2 * 2 + 2 = 4 + 2 = 6。因此 hmm(2) = 6
5. 再往上一层，我们得到 2 * 3 + hmm(2) = 6 + 6 = 12

如果你仔细观察，算法会计算:

2*x + ... + 4 + 2

我们可以反转它并分解出 2 并得到

2 * (1 + 2 + ... + x)。

这是一个arithmetic progression ，为此我们有一个众所周知的公式(即 x² + x)

需要多长时间？

渐近运行时间为O(n)。

没有循环，所以我们只需要计算递归的次数。人们可能会想计算计算的各个步骤，但这些 a 对于每一步都是恒定的，因此我们通常将它们组合成一个常数因子 k。

O(n) 是什么意思？

好吧...我们进行 x - 1 递归步骤，在每一步中将 x 减少 1 直到我们到达 x == 1。从x = n到x = 1有n - 1这样的步骤。因此，我们需要 k * (n - 1) 操作。

如果您认为 n 非常大，- 1 可以忽略不计，因此我们将其删除。我们还舍弃了常数因子，因为对于大的 n，O(nk) 和 O(n) 也没有太大区别.