algorithm - 递归算法的运行时间作为递归

Question

我遇到了一个问题，询问以下递归算法的运行时间是多少。

  int F(int A[ ],int N) {

    if(N==1)

    return 1 ;
    return F(A,N-1)+1
}

答案是 O(N)，但我只是不知道如何证明它的合理性。

标签： algorithmrecursionruntimerecurrence

Answer 1

您需要计算此函数正在进行的递归调用次数，以及在每个递归调用下完成的操作数。

所以每次调用函数时，有1个if调用，1个return调用。

递归调用的形式是，F(A,N-1)N 在每次调用中减 1，并且您的基本情况是 N=1，即当达到 1 时将不再有递归调用。

所以直观上很明显有N个递归调用，并且由于每个调用都是在恒定时间内进行操作（因此可以忽略不计），所以整体运行时间是O(N)

我希望这能解释。