复杂度

什么是算法？

算法是用于解决特定问题的一系列的执行步骤

效率。

斐波那锲数 (线性代数解法复杂度为O(1))

 // 复杂度高
 public static int fib(int n) {
	if (n <= 1) {
		return n;
	}
	return fib(n - 1) + fib(n - 2);
}
// 复杂度低
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;
}

public static void main(String[] args) {
	System.out.println(fib(45));
}

评判一个算法的好坏

单从执行效率上评估，比较不同算法对同一组输入的执行处理时间

上述方案比较明显的缺点：

1. 执行时间严重依赖硬件及运行时各种不确定环境因素
2. 必须编写相应的测试代码
3. 测试数据的选择比较难保证公正性

一般用一下纬度评估：正确性、可读性、健壮性、时间复杂度：估算程序指令的执行测试、空间复杂度

例子：以下方法的复杂度

  // 以下方法的复杂度
public static void text1(int n) {
	if (n > 10) {									// 1 + 4
		System.out.println("n > 10");
	} else if (n > 5) {
		System.out.println("n > 5");
	} else {
		System.out.println("n <= 5");
	}
	for (int i = 0; i < 4; i++) {
		System.out.println("test");
	}
}

public static void text2(int n) { // n
	for (int i = 0; i < n; i++) {
		System.out.println("text");
	}
}

public static void text3(int n) { // n^2
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			System.out.println("text");
		}
	}
}

public static void text4(int n) { // 48n
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 15; j++) {
			System.out.println("text");
		}
	}
}

public static void texst5(int n) { // log2(n)
	while ((n = n / 2) > 0) {
		System.out.println("test");
	}
}

public static void test6(int n) { // log5(n)
	while ((n = n / 5) > 0) {
		System.out.println("test");
	}
}

public static void test7(int n) { // nlog2(n)
	for (int i = 1; i < n; i += i) {
		for (int j = 0; j < n; j++) {
			System.out.println("test");
		}
	}
}

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);
	}
}

大O表示法

一般用大O表示法来描述复杂度，它表示的数据规模n对应的复杂度

• 忽略常数、系数、低阶

9 >> O(1)

• log2(n) 统一为 O(logn)

大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率，渐进时间表达式

O(1) < O(logn) < O(n) < O(nlogn) < O(n^3) < O(2^n) < O(n!) < O(n^n)

数据规模较小时：

数据规模较大时：

所以一开始的斐波那锲数的例子中，第一种方法的函数被调用多少次，决定函数的复杂度

问题在于重复调用

而第二种函数的复杂度为O(n)

所以：

算法优化方向

用尽量少的存储空间、用尽量少的执行步骤、

根据情况可以 空间换时间，时间换空间

多个数据规模的情况

最好、最坏复杂度

均摊复杂度

复杂度震荡

平均复杂度

练习算法的网站

leetcode
leetcode中文

斐波那锲数