作者GreatShot (我要拿Ph.D.!!!)
看板Programming
标题Re: [问题] 资料结构的意义
时间Tue Dec 5 02:25:16 2006
※ 引述《lovethree (lovethree)》之铭言:
: 我想请问一下,由於我是非科班,
: 我现在在学资料结构的时候,对於一些名词都觉得好像似懂非懂,像是时间复杂度,
: 时间复杂度在课本上好像没有讲的很仔细,还有很多种类的树,到底他们是要做什麽用?
: 我根本不知道树在应用层面的意义,请问一下,我有学过C,现在念资料结构还需要
: 什麽背景学科或是补充学科来加强的吗?
Data Structure比较像是方法
不管是不是科班 这科都是入门级的科目 所以不用担心
唯一需要的基础大概就是要会一点点基本的程式逻辑吧
他就是在教你怎样处理资料会 最省时间 or 最省空间 而已
什麽叫省时间 复杂度越低的越省时间
我打个比方
就像你的书房 你有20000本书
你的书要怎样放才能让你每次都在最快的时间内找到书
有新书要上柜的时候
又不用花太多时间搬移其他书才找的到位置放
之後却依旧能快速的找到想要的书
有整理过的复杂度就很低
因为你只要找几次就可以找到了
先找分类(文史类)-> 再找柜号 -> 按照字母排序找书 这样只需要做3次"找"的动作
假设你要找20本书
你就最多只要做20 x 3 = 60 次找的动作
如果你没有分类没有排序
你每在20000本书中找一本可能平均要花10000次找的动作
你要找20本书的话
就大约是10000^20次找的动作
60跟10000^20的差异是多少我想应该很明白了
这其实就是一种简单的资料结构(类似hash table)
Tree就是在做类似的事情
"让你资料找的快"
当然
你可以不会某些很高深的tree,或是某些很复杂的演算法
我打个比方吧
同样是念土木的
要盖水坝/101的工程师 跟要盖2层楼洋房的工程师
focus的东西是很不一样的
端看你的工作性质罗 没有所谓好坏 只有派不派的上用场罢了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.133.110.47
1F:→ fpga:应该是10000*20吧...10000^20有点惊人 61.230.217.65 12/05 15:41
2F:→ GreatShot:阿...手误 XD 220.133.110.47 12/05 23:39