本文共 2297 字，大约阅读时间需要 7 分钟。

数据结构和算法

1. 数据结构，是指一组数据的存储结构，算法，是指操作数据的一组方法；

2. 数据结构，是为算法服务的，算法，作用在特定的数据结构之上；

3. 数据结构和算法，解决的是如何更省，更快地存储和处理数据，而考量效率和资源消耗的方法，就是复杂度分析；

时间复杂度分析

1. 假设每行代码执行的时间都一样，为 unit_time，那么下面代码，执行时间 3 + 2n + 2n^2；

int cal(int n) {
    		int sum = 0; 		int i = 1; 		int j = 1; 		for (; i <= n; ++i) {
    			j = 1; 			for (; j <= n; ++j) {
    				sum = sum + i * j; 			}		} 	}

2. 因此代码执行时间 T(n) = O ( f ( n ) )，其中 n 表示每行代码的执行次数，f ( n ) 表示所有代码执行次数的总和，O 表示两者成正比；

3. 时间复杂度，表示代码执行时间，随数据规模增长的变化趋势，常量，系数，低阶并不能左右趋势，所以上面例子中的时间复杂度，就是 O ( n^2 )；

4. 所以分析算法时间复杂度的时候，只需关注循环执行次数最多的那一段代码，且常量执行时间，无论多大，都不能反映与数据规模相关的增长趋势，所以可以忽略；

5. 加法法则，总复杂度等于量级最大的那段代码的复杂度，乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；

6. 常见的时间复杂度 O ( log N )，下面的例子，执行 2⁰，2¹，2² … 2^x，2^x = n，就执行了 log2 N 次，因为无论 log 的底数是多少，都可以互相转换，log3 N = log3 2 * log 2 N，所以只要是对数执行次数，那么时间复杂度都是 O ( log N)；

i=1; 	while (i <= n) {
    		i = i * 2; 	}

7. 如果我们对 O ( log N ) 的代码，执行 N 次，那么该段代码的时间复杂度，就是 O ( N log N)；

空间复杂度

1. 空间复杂度，表示算法的存储空间，与数据规模之间的增长关系；

2. 下面的例子中，只有第三行，申请存储空间 n，其他代码都占常数存储空间，所以空间复杂度是 O ( n )；

void print(int n) {
     		int i = 0;  		int[] a = new int[n];  		for (i; i 
   
    = 0; --i) {
       			print out a[i]  		}	}
   

3. 常见的空间复杂度 O ( 1 )，O ( n )，O ( n^2 )；

最好，最坏，平均，均摊的时间复杂度

1. 通常使用一个复杂度，就可以满足需求，但如果同一块代码在不同的情况下，时间复杂度有量级的差距，就需要使用这三种复杂度，均摊时间复杂度，可以看作平均时间复杂度的一种分析方法；

2. 下面示例中，最好时间复杂度 O ( 1 )，最坏时间复杂度 O ( n )，根据概率论，查找的 x，出现在集合内的概率是 1 /2 ，循环执行 1 次的概率是 1 / 2n，执行 2 次的概率是 1 / 2n，执行 n 次的概率，是 1 / 2n + 1 / 2，所以平均复杂度是 (1 / 2n)* ( 1 + 2 + … + n) + n /2 = (n + 1) / 4 + n /2 = (3n + 1) / 4 ，所以平均复杂度是 O ( n )；

// n表示数组array的长度	int find(int[] array, int n, int x) {
     		int i = 0;  		int pos = -1;  		for (; i < n; ++i) {
       			if (array[i] == x) {
          				pos = i;       				break;    			} 		}  		return pos;	}

3. 下面的示例中， 最好时间复杂度 O( 1 )，最坏时间复杂度 O( n )，经过分析，最坏时间复杂度的出现，都是伴随着 n 次调用，出现一次，所以可以将最坏的一次，均摊到之前出现的 n -1 次上，所以均摊时间复杂度，就是 O( 1 )；

// array表示一个长度为 n 的数组 	// 代码中的array.length就等于n 	int[] array = new int[n]; 	int count = 0;  	void insert(int val) {
       		if (count == array.length) {
          			int sum = 0;       			for (int i = 0; i < array.length; ++i) {
             				sum = sum + array[i];       			}       			array[0] = sum;       			count = 1;    		}    		array[count] = val;    		++count; 	}

4. 如果算法操作中，大部分情况下时间复杂度都很低，只有个别情况下，时间复杂度比较高，而且这些操作之间，存在前后连贯的时序关系，这个时候，就可以考虑将这一组操作，放在一块儿分析，看是否能将较高时间复杂度的那次操作，平摊到其他那些时间复杂度比较低的操作上；

转载地址：http://xsfin.baihongyu.com/