1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

/**
 * 因为没有节省运算，所以实际上的算法复杂度还是 O(n)
 *
 * @param x
 * @param n
 * @return
 */
private static long functionBase(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }
    if (n % 2 == 1) {
        return functionBase(x, n / 2) * functionBase(x, n / 2) * x;
    } else {
        return functionBase(x, n / 2) * functionBase(x, n / 2);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * 将 function(x, n / 2) 提取出来，节省了乘法运算，所以算法复杂度为 O(logn)
 *
 * @param x
 * @param n
 * @return
 */
private static long function(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }
    long t = function(x, n / 2);
    if (n % 2 == 1) {
        return t * t * x;
    } else {
        return t * t;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

/**
 * 代码最简洁，但是时间复杂度爆炸
 * 时间复杂度为 2^(n-1),得出的结果是递归二叉树除根节点以外的节点数，即为调用次数
 * 空间复杂度为 O(n)
 * @param num Fibonacci 数列的第几个数 从 1 开始
 * @return
 */
public static long fibonacci0(int num) {
    if (num <= 1) {
        return 0;
    }
    if (num == 2) {
        return 1;
    }
    return fibonacci0(num - 1) + fibonacci0(num - 2);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 主要目的是减少递归调用的次数，导致上面这种递归的时间复杂度爆表的根本原因是一次递归里调用了两次自身，
 *<br/>
 * 这个算法的重点在于，直接用递归来从 f(1)、f(2) 开始计算第 n 个项的值，这样，求 f(n) 实际上只用计算 n 次，复杂度大大降低 为 O(n) ，太香了
 * 而 fibonacci0 是把 f(n) 拆分成 f(n-1)、f(n-2) 不停地往下拆分，一直拆分到 f(1)、f(2))
 * <br/>
 * 实际操作中，为了帮助理解，我们还可以添加 nowNum 变量，记录一下，我们算到那个变量了。如果和目标 num 相等即可返回
 *
 *
 * 空间复杂度为 O(n)
 *
 * @return
 */
public static long fibonacci1(long first, long second, int nowNum, int num) {
    if (num <= 1) {
        return 0;
    }else if (num == 2) {
        return 1;
    }else if(num == nowNum) {
        return first + second;
    }else{
        return fibonacci1(second, first + second, nowNum +1, num);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/**
 * 从 fibonacci1 中优化而来，可以看到，now 从 3 开始算，每次 +1，最终与 num 相等，拿其实可以直接用 num -1 最终等于 3，递归的次数是一样的，这样可以节约一个变量
 * @param first
 * @param second
 * @param num
 * @return
 */
public static long fibonacci2(long first, long second,int num) {
    if (num <= 1) {
        return 0;
    }else if (num == 2) {
        return 1;
    }else if(num == 3) {
        return first + second;
    }else{
        return fibonacci2(second, first + second, num-1);
    }
}