java - 递归方法的 Big-O 和 Big-Omega

Question

我的任务是尝试找到给定 Java 方法的 big-O 和 big-Omega，但不知道如何找到。我知道 big-O 给出了上限，big-Omega 给出了下限，但是在查看程序(更不用说递归程序)时，我到底如何弄清楚这一点呢？预先感谢您，这对我的学习有很大帮助。

public static boolean goal(int i, int n){
    if(n == 0){
        if( i == 91) {
            System.out.println("i = " + i +", DONE!!!");
            return true;
        }
        else {
            return false;
        }

    }
    else if(i % 2 == 1){
        if(goal(i + 53,n - 1))
        {
            System.out.println("i = "+ i + ", step # " + n);
            return true;
        }
        else
            return false;
    }
    else {
       if( goal(i + 53,n - 1) || goal(i / 2,n - 1))
       {
            System.out.println("i = "+ i +", step # " + n);
            return true;
       }
       else
            return false;
    }
}

Answer 1

每次递归迭代你都会将 n 减 1，当 N 达到 0 时递归停止，在最好的情况下你的 i 总是奇数，所以你进入第一个分支，所以这个算法的下界是 O(N)

上限是最坏的情况，是你的最后一个else分支，当你可以调用goal两次时，所以上限将为O(2^N)