A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 唐长智 中级黑马   /  2013-3-1 15:37  /  2280 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

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

评分

参与人数 1黑马币 +6 收起 理由
陈丽莉 + 6

查看全部评分

5 个回复

倒序浏览
时间复杂度就是执行算法所需要的时间(执行多少次赋值、比较、判断等操作),空间复杂度就是执行该算法需要消耗多少存储空间。
2者都是越低越好,但往往不能兼顾,需要找到时间和空间复杂度的平衡点。

评分

参与人数 1技术分 +1 收起 理由
陈丽莉 + 1 新人鼓励一下~

查看全部评分

回复 使用道具 举报
HM汪磊 发表于 2013-3-1 17:59
时间复杂度就是执行算法所需要的时间(执行多少次赋值、比较、判断等操作),空间复杂度就是执行该算法需要 ...

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

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

评分

参与人数 1技术分 +1 收起 理由
陈丽莉 + 1 鼓励一下~

查看全部评分

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

点评

你才万岁呢。。 0.0 我很公正的,不用这样  发表于 2013-3-2 10:00
回复 使用道具 举报
唐长智 发表于 2013-3-1 18:53
哦,那chrome浏览器就是个例子啊,我装的浏览器中感觉chrome的速度是最快的,但是,chrome是最占内存的。 ...

应该是这样的!!!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马