java - 为递归方法确定Big O

Question

我想弄清楚如何确定递归方法的大 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)) 包含什么？

Answer 1

取决于您如何看待它，它要么是 O(1)，因为对于正输入它总是最多需要 7 次迭代，您可以说它是 O(lg n)，因为所需的迭代次数会相对变化到输入的 lg base 2，或者它是未定义的，因为对于非正输入，计算永远不会完成。随你选吧!