算法时间复杂度学习
1. 算法
算法：是用于解决特定问题的一系列的执行步骤。
举例：
//计算 a + b的和
public static int add( int a, int b){
return a + b;
}
//计算 1 + 2 + 3 + 4 + ... n 之和
public static int sum( int n){
int sum = 0;
for (int i = 0; i <= n; i ++ ){
sum += i;
}
return sum;
}
简单的求两数之和，以及求n个数之和，都是算法。
但是，相同的结果，不同的方法效率天差地别。
示例：
//计算 1 + 2 + 3 + 4 + ... n 之和
public static int sum1( int n){
int sum = 0;
for (int i = 0; i <= n; i ++ ){
sum += i;
}
return sum;
}
//计算 1 + 2 + 3 + 4 + ... n 之和
public static int sum2( int n){
return n * (n + 1) / 2;
}
由以上示例可以发现，1 + 2 + 3 + 4 + ... n：
- 使用sum1方法使用for循环累加；
- 使用sum2数学归纳的公式：n * (n + 1) / 2；
两种实现方式，在 n 较小时可能看不出太大差别，但是当n足够大时，sum2 执行的步骤明显少于sum1方法，效率也更高。
1.1 如何判断一个算法的好坏
如果单从执行效率上进行评估，可能会想到这么一种方案：比较不同算法对同一种输入的执行处理时间，这种方法叫做 事后评估法；
一般从以下几个维度来评估算法的优劣：
- 正确性，可读性，健壮性（对不合理输入的反应能力和处理能力）
- 时间复杂度（time complexity）：估算程序指令的执行次数 （执行时间）
- 空间复杂度（space complexity）：估算所需占用的存储空间
2. 时间复杂度
对于我们常说的时间和空间复杂度，都是估算；
因为当我们的数据规模极大的时候，估算更为合适；
示例：
public static void test1(int n) {
// 执行1次
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
//执行 4 次
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
//总执行： 1 + 4 = 5次
}
public static void test2(int n) {
for (int i = 0; i < n; i++) {
System.out.println("test");
}
// 总执行 1 + n + n + n = 3n + 1次
}
public static void test3(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 总执行：3n^2 + 3n + 1次
}
public static void test4(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 总执行：48n + 1次
}
public static void test5(int n) {
while ((n = n / 2) > 0) {
System.out.println("test");
}
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 执行次数 = log2(n)
}
public static void test6(int n) {
while ((n = n / 5) > 0) {
System.out.println("test");
}
// 执行次数 =log5(n)
}
public static void test7(int n) {
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
//总执行次数： 1 + 3*log2(n) + 2 * nlog2(n)
}
对于n阶for循环，初始化i = 1 执行1次；i < n，执行n次；i ++执行n次；print执行n次，所以一般for循环执行的次数：3n + 1
2.1 大O表示法
一般用大O表示法来表示时间或空间复杂度，它表示数据规模对应的复杂度；
大O表示法特点：
-
忽略常数，系数，低阶
- 9 >> O(1)
- 2n + 3 >> O(n)
- log2(n)、log3(n) >> O(log(n))
- nlog2(n) + 5 >> O(nlog(n))
- n^2 + 2n + 6 >> O(n^2)
- n^3 + 4 * n^2 + 2n + 6 >> O(n^3)
所以对应test1-test7示例的复杂度：
- test1 >> O(1)
- test2 >> O(n)
- test3 >> O(n^2)
- test4 >> O(n)
- test5 >> O(log(n))
- test6 >> O(log(n))
- test7 >> O(nlog(n)
注意：大O估算法仅仅是一种粗略的估算模型，能短时间内了解一个算法的估算效率。
3. 斐波那契数
简单算法示例： 求第n个斐波那契数 （第一个数为0，第二个数为1 ，第n个数为前两个数n-1 和 n-2之和 ）
方法1：迭代实现
/**
* 0 1 2 3 4 5 6 7 .....n
* 0 1 1 2 3 5 8 13 ....?
*
* */
public static int fib(int n){
if (n <=1) return n;
return fib(n -2) + fib( n -1);
}
方法2：for循环实现
/*
*for循环执行n-1次
*
* **/
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;
}
方法3： while循环
public static int fib3(int n){
if(n <= 1) return n;
int first = 0;
int second = 1;
while(n-- > 0) {
second += first;
first = second - first;
}
return second;
}
复杂度对比：
-
fib：O（2^n）
fib复杂度-摘自小码哥课件 fib2：使用for循环，复杂度估计为O（n）
fib3：与for循环差别不大，复杂度估计为O（n）
简单看来，fib实现方式易于理解，且代码较少，但从时间复杂度来看，fib2的性能大大的高于fib；
如果有一台1GHz的计算机，运算速度为10^9每秒
-
当n=64时；
fib：O（2^n） 耗时584.94年
fib2与fib3：O（n） 耗时6.4 * 10 ^(-8)秒（纳秒级别）
