我先强调一下
请侧重注意时间复杂度,不要在意语句的作用
先上一下斐波那契的代码(解释在注释里面)
跟语言没关系,都差不多啦,大家想看别的语言的解释
没学过Java也能看,只是它在第一个,我就直接复制了(真的)
力扣
先上只看时间复杂度的句子
class Solution {
static final int MOD = 1000000007;
public int fib(int n) {
if (n < 2) {
return n;
}
int[][] q = {{1, 1}, {1, 0}};
int[][] res = pow(q, n - 1);//pow的时间复杂度为对数级,pow函数里面的注释解释了
// 到这里应该清楚对数级是可以算的了吧
return res[0][0];
}
// pow时间复杂度为lgn级别
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
// 大于等于1也可以
if ((n & 1) == 1) {
// 注意mutiply里面没有递归
ret = multiply(ret, a);//multiply时间复杂度:常数级别,可以自己分析一下
}
n >>= 1;//相当于整除以2,这里是关键哦!!!!!
// 就是以前的练习题哦,大家应该会
// 算这个只看while的时间复杂度,控制循环次数应该就是这一句
// 这个是你想要的解释吗??
a = multiply(a, a);
}
return ret;
}
//自己先分析一下
//时间复杂度:常数级别
//时间复杂度:常数级别
//时间复杂度:常数级别
//时间复杂度:常数级别
//时间复杂度:常数级别
//我就强调一下,要不可能被忽略
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++)
{
c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
}
}
return c;
}
}
public class hello {
public static void main(String[] args) {
int n = 8;
n = n&1;
System.out.println(n);
// Solution s = new Solution();
// System.out.print(s.fib(2));
}
}
上一遍有一些解释语句,不单单只解释复杂度
class Solution {
static final int MOD = 1000000007;//然后取模用的数字
//想法是0,1,1,2,3,5那么n就是下标
//注意n是下标
public int fib(int n) {
if (n < 2) {
return n;
}
int[][] q = {{1, 1}, {1, 0}};
// 1,0分别是第2项,和第1项
// 1,1分别是第3项,和第2项
// 继续写
// 2,1分别是第4项,和第3项
// pow函数的定义在下面
int[][] res = pow(q, n - 1);//pow的时间复杂度为对数级,pow函数里面的注释解释了
// 到这里应该清楚对数级是可以算的了吧
return res[0][0];
}
// pow时间复杂度为lgn级别
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
// 或者大于等于1
// n & 1 这是位计算
// 结果等于0,n就是偶数
// 1,n就是奇数
if ((n & 1) == 1) {
// mutiply的定义在下面
// 注意mutiply里面没有递归
ret = multiply(ret, a);//multiply时间复杂度:常数级别,可以自己分析一下
}
// 以13>>1为例,首先将13转换为二进制形式1101,
// 然后右移1位,最低位丢弃,最高位使用符号位0补充,
// 得110,转换为十进制数为6,相当于13/2
n >>= 1;//相当于整除以2,这里是关键哦!!!!!
// 就是以前的练习题哦,大家应该会
// 算这个只看while的时间复杂度,控制循环次数应该就是这一句
// 这个是你想要的解释吗??
// mutiply的定义在下面
a = multiply(a, a);
}
return ret;
}
//用到矩阵的知识了
//没学过的就先不用理解mutiply的作用了
//但你一定清楚mutiply的时间复杂度吧
//时间复杂度:常数级别
//时间复杂度:常数级别
//时间复杂度:常数级别
//时间复杂度:常数级别
//时间复杂度:常数级别
//我就强调一下,要不可能被忽略
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++)
{
c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
}
}
return c;
}
}
//如果你的想法是0,1,1,2,3,5那么n就是下标
//是1,1,2,3,5那么n是位序
public class hello {
public static void main(String[] args) {
int n = 8;
n = n&1;
System.out.println(n);
// Solution s = new Solution();
// System.out.print(s.fib(2));
}
}
求平方
有异曲同工之妙
class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
public double quickMul(double x, long N) {
if (N == 0) {
return 1.0;
}
//这一句请分析分析,看看是不是和while很像
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
}
怎么样,是不是看完了,又不知道之前自己为什么不懂了,哈哈,拿笔算一算就好啦