单选题 适中
#20280

下述斐波那契数列计算的时间复杂度是?( ) int fibonacci ( int n ) { if ( n == 0 ) return 0 ; if ( n…

下述斐波那契数列计算的时间复杂度是?( )

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:D
解析

斐波那契数列的递归存在 重复计算,每个 fibonacci(n) 调用会进一步分解为 fibonacci(n-1) 和 fibonacci(n-2),调用次数和2^n有关,时间复杂度为O(2^n)。