黑马程序员技术交流社区

标题: 算法数据结构的问题。 [打印本页]

作者: 唐长智 时间: 2013-3-1 15:37
标题: 算法数据结构的问题。
今天在一个博客里看到一个关于新手学java的通病的帖子。发现上面的问题我都没办法解答。
我的专业不是计算机，编程一类的，所以在数据结构和算法上可以说是一窍不通，希望有科班出身的大牛来解答一下下面的问题，如果有好的关于这方面的电子书也分享分享啊。
★什么时候该用数组型容器、什么时候该用链表型容器？
★什么是散列函数？HashMap的实现原理是什么？
★什么是算法复杂度？
★如何否理解空间换时间的思想？

作者: HM汪磊 时间: 2013-3-1 17:59
时间复杂度就是执行算法所需要的时间（执行多少次赋值、比较、判断等操作），空间复杂度就是执行该算法需要消耗多少存储空间。
2者都是越低越好，但往往不能兼顾，需要找到时间和空间复杂度的平衡点。

作者: 唐长智 时间: 2013-3-1 18:53

HM汪磊发表于 2013-3-1 17:59
时间复杂度就是执行算法所需要的时间（执行多少次赋值、比较、判断等操作），空间复杂度就是执行该算法需要 ...

哦，那chrome浏览器就是个例子啊，我装的浏览器中感觉chrome的速度是最快的，但是，chrome是最占内存的。就是用空间来换时间吧。

作者: 杜鹏飞 时间: 2013-3-1 19:10
1.
这个问题不好回答，我只能给你说一说两者的优缺点。
数组的优点是占用内存较少，可以快速定位，缺点是，比如说，我们要向数组的某位置插入一个数，那么，数组后面的数都要移动吧，而链表可以快速完成该操作，缺点是其占用内存较多，操作也较复杂。
2.
关于散列函数，它的核心用途就是合理利用资源。比如你要对一堆数排序，数的数量比较少，但最大的数可能是10^9，那么用数组既没办法存储，就算能存储也会浪费空间，散列技术可以同时解决以上两个问题。
3.
关于算法复杂度，这涉及两个概念，即时间复杂度与空间复杂度。
时间复杂度用来衡量算法解决某数据量时效率，空间复杂度衡量算法解决该问题是所用的空间。
4.
既有时间换空间，也有空间换时间，这些技巧多出现在某些ICPC题目中，比较无聊。

书籍的话，如果楼主不说明自己的“水平”（数学，计算机等等），是没办法推荐的。

作者: 赵海洋 时间: 2013-3-1 22:11
我可得好好回答，认真分析你的每一句话，斑竹对我的回答有意见了。。。。
首先说下数据结构，它里面的算法，我个人学习的时候感觉格式不是很严格，因为当时学的时候是用c学的，然后有很多时候写的是伪代码，所以楼主想学的话，个人认为，基础学完你如果肯用心数据结构应该能学懂。至于书籍，由于笔者学的c版的数据结构，就没办法推荐了，我打算学完java基础后学一下java的数据结构，有什么好书告诉我一下，嘿嘿。你说的这些问题应该能回答一点，如果不对请各位指证。
第一个问题：
至于这个数组型和链表型，说说各自优缺点吧，数组型，随机查找，你想把数据插入到哪里，直接插入即可。因为它的下脚标就可以定位，但是数组内插入一个数那就麻烦了，需要移动这个数以后的所有元素，代码是个for循环类型，平均移动元素个数是[n(n-1)]/2（我记得是这个）。
链表，顺序查找，各个节点之间是用指针连接，不能想把数据插到哪就插到哪。但是不需要移动很多其他元素，只需要改变指针的指向，所以移动元素基本没有。
第二个问题：
散列函数又叫做hash(哈希)函数，hash就是找到一种数据内容和数据存放地址之间的映射关系。同样的，也有哈希文件这种文件类型。哈希函数，额，我想想咋说啊。。。就是你任意输入一段数据（也可能是其他），然后输出的是固定长度的。由此可见，这东东要是用到加密解密上不就爽了，事实上也是如此，例如MD5就是用到了散列函数，还有数字签名等。
第三个问题：
算法复杂度，算法复杂度分为时间复杂度和空间复杂度，通常一个算法的效率使用平均时间复杂度的形式给出，而我们分析时间复杂度是根据代码在最坏情况下的执行时间来分析，求平均时我感觉你只要把代码执行顺序和是否递归循环等弄懂，你应该能求出平均时间复杂度。
至于空间复杂度，是你这个算法运行所占用的内存，我喜欢称它为执行的代价，我接触的大多数排序算法的空间复杂度都是O(1)，当然有例外，例如基数排序就不是。
时间换空间，空间换时间：
我的回答是来自我看的操作系统这本书，这应该是运用到局限性原理，应用到缓冲技术，虚拟技术等，就是一组数据被调用，那么他有可能被重复调用，这是时间局限性，而有一组数据被调用，其附近数据也可能被调用，这是空间局限性，由此引发出时间换空间，空间换时间思想。不知道这段关于操作系统书上的内容是不是回答了你的第四个问题。
斑竹万岁。。。。

作者: HM汪磊 时间: 2013-3-2 12:17

唐长智发表于 2013-3-1 18:53
哦，那chrome浏览器就是个例子啊，我装的浏览器中感觉chrome的速度是最快的，但是，chrome是最占内存的。 ...

应该是这样的！！！

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2