文档章节

软考程序员课程精讲之Trie树的优点

软考希赛教育
 软考希赛教育
发布于 2017/06/26 17:43
字数 568
阅读 4
收藏 0

   欲参加2017年下半年软考程序员考试的同学,现在可以着手复习了。下面是希赛小编为大家整理的部分软考程序员课程中的知识点,下文主讲Trie树的优点。供各位学习。      

       Trie树的优点举例

       已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

       1.最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。

       2.使用hash:我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)*O(1)=O(n)。

       3.使用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len),而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(n*len),实际查询的复杂度只是O(len)。

       解释一下hash为什么不能将建立与查询同时执行,例如有串:911,911456输入,如果要同时执行建立与查询,过程就是查询911,没有,然后存入9、91、911,查询911456,没有然后存入9114、91145、911456,而程序没有记忆功能,并不知道911在输入数据中出现过。所以用hash必须先存入所有子串,然后for循环查询。

       而trie树便可以,存入911后,已经记录911为出现的字符串,在存入911456的过程中就能发现而输出答案;倒过来亦可以,先存入911456,在存入911时,当指针指向最后一个1时,程序会发现这个1已经存在,说明911必定是某个字符串的前缀。

 

© 著作权归作者所有

共有 人打赏支持
软考希赛教育
粉丝 1
博文 104
码字总数 98019
作品 0
长沙
私信 提问
算法 | 动画+解析,轻松理解「Trie树」

Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。 此外 Trie 树也称前缀树(因为某节点...

AI科技大本营
01/06
0
0
软考说明会【北京】

软考是由国家人事部和信息产业部领导下的国家级考试。该考试由于其权威性和严肃性,得到了社会及用人单位的广泛认同。通过考试获得证书的人员,在IT能力提升、升职加薪、资质代评、个人职业发...

345木头人
2017/08/02
0
0
Google 面试题 | 字典里面的最长单词

专栏 | 九章算法 网址 | http://www.jiuzhang.com 三角形分割线 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案...

2018/02/10
0
0
软考程序员课程精讲之最小生成树

最小生成树 如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树。生成树是连通图包含图中的所有顶点的极小连通子图。值得注意的是,图的生成树并不唯一。从不同的顶点出...

软考希赛教育
2017/05/04
2
0
Trie 树实现与应用

Trie树 基本概念  Trie树又称字典树,它是用来查询字符串的一种数据结构。它每一个节点都有26个子节点,所以是26叉树。优点查询字符串的时候速度快,缺点浪费大量空间。  当一个字符串长为...

sdoyuxuan
2018/01/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

图像库stb_image

https://github.com/nothings/stb 目前一般主流的图像格式也就是bmp,jpg,png,tga,dds,除了DDS一般是给DX用的,虽然一堆OpenGL程序也有用的,但是我一般只用png和tga, png不用说了,带a...

robslove
17分钟前
1
0
Spring 事务提交回滚源码解析

前言 在上篇文章 Spring 事务初始化源码分析 中分析了 Spring 事务初始化的一个过程,当初始化完成后,Spring 是如何去获取事务,当目标方法异常后,又是如何进行回滚的,又或是目标方法执行...

TSMYK
36分钟前
2
0
百度黄埔学院将培养一批首席AI架构师,为“国之重器”赋能

深度学习高端人才不仅是AI发展的重要养分,也是企业转型AI巨大推动力。2019年1月19日,百度黄埔学院——深度学习架构师培养计划在百度科技园举行开学典礼,深度学习技术及应用国家工程实验室...

深度学习之桨
今天
3
0
扒站wget仿站

wget -c -r -p -np -k http://xxx.com/xxx 其中: -c, --continue (断点续传) 接着下载没下载完的文件 -r, --recursive(递归) specify recursive download.(指定递归下载) -p, --page...

临江仙卜算子
今天
2
0
Nextjs+React非页面组件SSR渲染

@随风溜达的向日葵 Nextjs Nextjs是React生态中非常受欢迎的SSR(server side render——服务端渲染)框架,只需要几个步骤就可以搭建一个支持SSR的工程(_Nextjs_的快速搭建见Next.js入门)...

随风溜达的向日葵
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部