算法的空间复杂度

续上节《--算法的时间复杂度--》https://www.cnblogs.com/nbk-zyc/p/12293186.html

1 算法的时间复杂度

　　常见算法的时间复杂度

　　常见算法的时间复杂度比较：

　　时间复杂度的案例分析：

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 /**
 6  * 功能： 查找数组下标并返回
 7  * 参数：
 8  *  a[]： 输入数据
 9  *  n：数组长度 
10  *  v：待查找的元素
11  * 返回值：待查找元素的数组下标
12 */
13 int find(int a[], int n, int v)
14 {
15     int ret = -1;
16 
17     for(int i = 0; i < n; i++)  // O(n)
18     {
19         if( a[i] == v)
20         {
21             ret = i;
22             break;
23         }
24     }
25 
26     return ret;
27 }
28 
29 
30 
31 int main(int argc, char* argv[])
32 {
33     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
34     int length = sizeof(arr)/sizeof(int);
35     int min = find(arr, length, 1);     // 最好情况，算法执行1次，O(1)
36     int max = find(arr, length, 10);    // 最差情况，算法执行10次，O(10)
37 
38     return 0;
39 }

查找数组下标并返回

　　结论：一般来说，算法的时间复杂度需要考虑其最坏的情况，因为只有这样，才能满足其最好情况和平均情况。（上节内容都是基于算法的时间复杂度的最坏情况考虑的）

2 算法的空间复杂度（Space Complexity）

　　1）定义：

　　　　对一个算法在运行过程中临时占用存储空间大小的度量，记作 S(n) = S(f(n)) --- 可以使用算法的时间复杂度来估算算法的空间复杂度（内存分配）

　　　　　　　　n: 问题规模

　　　　　　　　f(n):空间使用函数，与 n 有关

　　2）代码展示：

 1 // sum1() 空间复杂度 = n+4
 2 long sum1(int n)    // 1
 3 {
 4     long ret = 0;   // 1
 5     int* array = new int[n];    // n
 6     
 7     for(int i=0; i<n; i++)  // 1
 8     {
 9         array[i] = i + 1;
10     }
11     
12     for(int i=0; i<n; i++)  // 1
13     {
14         ret += array[i];
15     }
16     
17     delete[] array;
18     
19     return ret;
20 }

空间复杂度练习

　 3）空间与时间的策略

　　　　1. 通常算法的时间复杂度更让人关注；

　　　　2. 如果有必要，可以通过增加额外空间来降低时间复杂度；（空间换时间）

　　　　3. 同样，也可以通过增加算法的耗时来换取空间复杂度；（时间换空间）

 1 /*
 2     问题： 
 3     在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。
 4     设计一个算法，找出出现次数最多的数字。
 5 */
 6 
 7 #include <iostream>
 8 
 9 using namespace std;
10 
11 int search(int a[], int len)
12 {
13     int sp[1000] = {0}; // 初始化每个自然数出现的次数，数组下标加1代表当前的自然数
14     int max = 0;    // 保存自然数出现次数的最大值
15     int ret = 0;    // 保存出现次数最多的自然数
16     
17     for(int i=0; i<len; i++)
18     {
19         sp[a[i] - 1]++; // 标记自然数的出现次数
20     }
21     
22     for(int i=0; i<1000; i++)
23     {
24         if( max < sp[i] )
25         {
26             max = sp[i];
27         }
28     }
29     
30     for(int i=0; i<1000; i++)
31     {
32         if( max == sp[i] )
33         {
34             ret = i + 1;
35             break;
36         }
37     }
38 
39     return ret;
40 }
41 
42 int main(int argc, char* argv[])
43 {
44     int a[] = {1, 1, 3, 4, 5, 6, 6, 6, 3, 3, 6};
45     
46     int ret = search(a, sizeof(a)/sizeof(*a));
47     
48     cout << ret << endl;
49 
50     return 0;
51 }

空间换取时间的代码展示

代码中核心思想：

思考题：当两个算法的大O表示法相同时，是否意味着这两个算法效率完全相同？

　　　　答：两个算法的大O表示法相同，只代表这两个算法效率的数量级相同。

重点提示：

　　1）一般而言，工程中使用的算法，时间复杂度不超过O(n3)；

　　2）算法分析与设计时，重点考虑最坏情况下的时间复杂度；

　　3）大O表示法同样适用于算法的空间复杂度；

　　4）空间换时间是工程开发中常用的策略。