算法的空间复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法的空间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3392字，纯文字阅读大概需要5分钟。

内容图文

续上节《--算法的时间复杂度--》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）空间换时间是工程开发中常用的策略。

 

内容总结

以上是互联网集市为您收集整理的算法的空间复杂度全部内容，希望文章能够帮你解决算法的空间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---