简介：
如果想对数据结构和算法有基本的了解和认识，那么算法复杂度是前提，算法复杂度包含时间复杂度和空间复杂度，具体概念性的问题自己可自行查找，我们重点来看一下如何计算时间复杂度。
时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
空间复杂度（space complexity）：估算所需占用的存储空间
时间复杂度
1.先看一个简单的，这个需要执行一次，时间复杂度为O(1)
public static void test0(int n) {
// 汇编指令
System.out.println("test"); //需要执行1次
}
2.下面的方法，我们进行一个解析，首先 int i = 0;执行一次， i < 4;执行4次，i++执行4次，for循环里面执行4次，所以会执行1+4+4+4=13次，时间复杂度为O(1)
public static void test1(int n) {
// 汇编指令
// 1 + 4 + 4 + 4
// O(1)
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
}
3.同上，如果把常量变为变量n，那下面执行次数就变成了1+3n，时间复杂度为O(n)
public static void test2(int n) {
// O(n)
// 1 + 3n
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
4.如果for循环嵌套一个for循环该怎么计算呢，可以看到外for循环会执行1+2n次，而里面的for循环会执行n次的遍历，即n*(1+3n),
则共执行3n^2 + 3n + 1次，时间复杂度为O(n^2)
public static void test3(int n) {
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
// O(n^2)
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
5.上面的算法都比较常规，我们看下面这种如何分析；
我们首先使用假设的方式来推算，假设n=8那么
n 的取值分别是4（一次） 2（二次） 1（三次）会执行三次，
同理可推 n=16时，会执行4次，也就会得到一个关系
执行次数 = log2(n)，时间复杂度为O(logn)
public static void test5(int n) {
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 执行次数 = log2(n)
// O(logn)
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
在上面的方法中，如果将(n = n / 2) > 0换成了(n = n / 5) > 0也同样适用，即此时的执行次数 = log5(n)
6.下面是对上面的一种变形，i += i等价于i = i*2，实际上就是n=122*2···，即可知需要log2(n)次，时间复杂度为O(nlogn)
public static void test7(int n) {
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(nlogn)
for (int i = 1; i < n; i += i) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
空间复杂度
1.下面这个主要用来体现空间复杂度的，从 int[] array = new int[n];可以看出空间复杂度为O(n)，其他的都是常量
public static void test10(int n) {
// O(n)
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
}
斐波那契数列算法分析
数字谜题：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...
数学表示：
Fibonacci数列的数学表达式就是：
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1
1.递归算法，时间复杂度O(2^n)
// O(2^n)
public static int fib1(int n) {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}
1 + 2 + 4 + 8 = 20 + 21 + 22 + 23 = 24 − 1 = 2n−1 − 1 = 0.5 ∗ 2n − 1
所以复杂度为O(2^n)
2.迭代算法，时间复杂度O(n)
// O(n)
public static int fib2(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
