1

我试图弄清楚如何确定递归方法的大 O 表示法。我意识到这可能与迭代方法相同，但我不确定这一点。

我编写了这个简单的递归 Java 程序：

public RecursiveFunctions() {
recursiveFunction1(2);
}

// Meget simpel rekursiv metode der taeller en Integer ned 
public void recursiveFunction1(int someInteger) {
    System.out.println("Tallet er nu : " + someInteger);
    someInteger = someInteger * 2;
    if (someInteger < 100) {
        recursiveFunction1(someInteger);            
    }
}

我不确定这一点，但我的猜测是这是 O(n) 还是 O(1) 表示法？另外，O(n^2) 或 O(log(n)) 包含什么？

4

3 回答 3

4

根据你的看法，它要么是 O(1)，因为对于正输入，它总是最多需要 7 次迭代，你可以说它是 O(lg n)，因为所需的迭代次数将相对于 lg输入的基数 2，或者它是未定义的，因为对于非正输入的计算永远不会完成。任你选！

于 2013-06-16T20:03:48.457 回答
1

您必须确定基本案例的成本（函数 C(n)）和递归调用的成本。例如，对于阶乘函数：

unsigned int factorial(unsigned int n)
{
    if(n < 2) //This is O(1), so not affect to the result (We could think as its a constant 'a')
        return 1; //As the comparison, think its a constant 'b', so C(0) and C(1) = b + a;
    else
        return n * factorial(n-1); //The multiplication (O(1), a constant 'c') and the call C(n-1), so C(n) = c + a + C(n-1)
}

现在，将函数 C(n) 扩展为一组值，以找到一个级数：

C(0) = a + b
C(1) = a + b
C(2) = (c+a) + C(1) = (c+a) + a + b
C(3) = (c+a) + C(2) = (c+a) + (c+a) + C(1) = (c+a) + (c+a) + a + b
C(4) = (c+a) + C(3) = (c+a) + (c+a) + C(2) = (c+a) + (c+a) + (c+a) + C(1) = (c+a) + (c+a) + c + a + b
C(5) = (c+a) + C(4) = (c+a) + (c+a) + C(3) = (c+a) + (c+a) + (c+a) + C(2) = (c+a)  + (c+a) + (c+a) + (c+a) + C(1) = (c+a) + (c+a) + (c+a) + (c+a) + a + b
...
C(n) = (n-1)*(c+a) + a + b --> O(n)

但是认为大 O 仅对大 n 有意义，而不是小数字，就像在您的代码中那样（您的代码至少执行七次调用，这相当于 O(1)）。

于 2013-06-16T20:14:13.660 回答
0

一般来说，找到递归方法的渐近增长可能非常复杂，但这个任务通常可以使用Master theorem来解决。

你的例子太简单了。它可以很容易地转换为具有几乎等效性能的迭代函数。然后你可以找到迭代方法的Big-O（看起来你知道怎么做）。

于 2013-06-16T20:18:29.730 回答