Fibonacci 数列O(logn)解法
传统解法
提到斐波那契数列（Fibonacci Sequence），首先想到的是经典的动规（DP）算法。
时间复杂度O(n)，这里空间复杂度可以优化到O(1)。代码如下：
int fib_n(int n) { int dp[3] = {1, 1}; if (n <= 1) return dp[n]; for (int i = 2; i <= n; ++i) dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3]; return dp[n % 3]; }
但是初次接触O(logn)解法有如醍醐灌顶，叹为观止……
O(logn)解法
思路来源 1
考虑一个求幂运算。比如求an，一般来说需要n次累乘，时间复杂度显然是O(n)。实际上可以通过递归达到一种更优化的效果：
an = (an/2)2 * an%2
这里的n/2是取整，如5/2=2。这样就可以实现相当于二分的效果，时间复杂度为O(logn)。
思路来源2
对于Fib数列an(n ≥ 0)，可以通过矩阵乘法的方式进行递推：
进而可以得到：
这样就（很机智地）把Fib数列问题转化成了一个求矩阵幂的运算。
解题方法
结合以上思路，首先将其转化为矩阵求幂问题，然后进行二分，O(logn)解法由此诞生。再次感慨人类清奇的脑洞 _(:з」∠)_
以下是代码：
int** mult(int** m1, int** m2)
{
int** res = new int*[2];
for (int i = 0; i < 2; ++i) res[i] = new int[2];
res[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
res[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
res[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
res[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
return res;
}
int** recur(int x)
{
if (x == 0) {
int** res = new int*[2];
for (int i = 0; i < 2; ++i) res[i] = new int[2];
res[0][0] = res[1][1] = 1;
res[0][1] = res[1][0] = 0;
return res;
}
if (x == 1) {
int** res = new int*[2];
for (int i = 0; i < 2; ++i) res[i] = new int[2];
res[0][1] = res[1][0] = res[1][1] = 1;
res[0][0] = 0;
return res;
}
int** half = recur(x / 2);
return mult(mult(half, half), recur(x % 2));
}
// time: O(logn)
int fib_logn(int n)
{
if (n == 0 || n == 1) return 1;
int** mat = recur(n - 1);
return mat[0][1] + mat[1][1];
}
{
int** res = new int*[2];
for (int i = 0; i < 2; ++i) res[i] = new int[2];
res[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
res[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
res[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
res[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
return res;
}
int** recur(int x)
{
if (x == 0) {
int** res = new int*[2];
for (int i = 0; i < 2; ++i) res[i] = new int[2];
res[0][0] = res[1][1] = 1;
res[0][1] = res[1][0] = 0;
return res;
}
if (x == 1) {
int** res = new int*[2];
for (int i = 0; i < 2; ++i) res[i] = new int[2];
res[0][1] = res[1][0] = res[1][1] = 1;
res[0][0] = 0;
return res;
}
int** half = recur(x / 2);
return mult(mult(half, half), recur(x % 2));
}
// time: O(logn)
int fib_logn(int n)
{
if (n == 0 || n == 1) return 1;
int** mat = recur(n - 1);
return mat[0][1] + mat[1][1];
}
结果比较
简单比较一下后者的优化效果，为了是效果更明显，这里将参数设置成一个较大的数（如109），以下是代码以及结果：
void test() { const int num = 1e9; clock_t t1, t2; t1 = clock(); fib_n(num); t2 = clock(); printf("O(n): %.4f s\n", (double)(t2 - t1) / CLOCKS_PER_SEC); t1 = clock(); fib_logn(num); t2 = clock(); printf("O(logn): %.4f s\n", (double)(t2 - t1) / CLOCKS_PER_SEC); }
结果
O(n)算法的速度达到了男子百米的世界顶级水平，而O(logn)只表现出一脸不屑……
好吧，我服……那我把logn的多跑几次 for (int i = 0; i < 100; ++i) fib_logn(num);
那么结果也很明显了，O(logn)算法表现惊艳！
投递腾讯等公司7个岗位 >
北京云智软通信息技术有限公司西安分公司二面9人在聊