算法性能分析

求x的n次方

时间复杂度尽可能小。

int function4(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

求斐波那契数列

需要优化。

// 版本二
int fibonacci(int first, int second, int n) {
    if (n <= 0) {
        return 0;
    }
    if (n < 3) {
        return 1;
    }
    else if (n == 3) {
        return first + second;
    }
    else {
        return fibonacci(second, first + second, n - 1);
    }
}

// 调用fibonacci(1, 1, n);

解释：

当n<=0，返回0（因为没有数）
当n<3，返回1（因为前两项都是1）
当n==3，返回first+second（因为等于前两项相加）
当n>3，每次相加之后，新的一项等于前两项相加。而second表示新的一项（相当于往右移了一位）

递归算法空间复杂度的计算

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

二分递归的性能分析

int binary_search( int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x);
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}