文档章节

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

软考希赛教育
 软考希赛教育
发布于 2017/06/26 17:43
字数 568
阅读 4
收藏 0
点赞 0
评论 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
长沙
Google 面试题 | 字典里面的最长单词

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

02/10
0
0
我的CCIE自学之路

写在最前面 最近发现很多在校生/初入社会的年轻人,比较迷茫… 下面给大家分享一下我的网络工程师自学之路,希望对大家有所帮助。本人就读于某矿业大学,信息安全专业(这个跟在音乐院校,学...

永恒2222
2017/11/01
0
0
Trie 树实现与应用

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

sdoyuxuan
01/24
0
0
Trie Tree 实现中文分词器

Trie Tree 简介 Trie Tree,又称单词字典树、查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频...

大海之中
07/18
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
(最新)2017年下半年软考各科历年真题及答案解析

【徐朋出品,必属精品】作为51CTO学院的软考特级讲师,本着对广大学员负责的态度,在每年同学们参加完软考考试,我都会尽早的给大家发布各科的真题详细解析资料。一方面是为了帮助参加软考考...

软考徐朋
2017/11/20
0
0
2017年11月软考全国各省市报名时间及报名网址(动态更新)

徐朋老师:10年以上软考培训经验,线下培训学员过万人。培训过的课程有:网络规划设计师、网络工程师、信息系统项目管理师、系统集成项目管理师、信息安全技术、网络技术、信息安全工程师、软...

软考徐朋
2017/08/02
0
0
读者们有福啊!部分真题或取材或思路借鉴于相关辅导书

读者们有福啊! 我大致看了一下相关QQ群及论坛,从网友们零星发出的试题中,感觉此次中级、高级项目经理考试试卷中的一些试题,或取材、借鉴于我的相关图书。 例如,中级系统集成项目管理工程...

wg_wg
06/29
0
0
Internet路由之路由表查找算法概述-哈希/LC-Trie树/256-way-mtrie树

说明:本文没有源码分析的内容,然而我认为能理解本质比能看懂源码更有用,因为理解了本质之后,你也许就不用再看源码了,你甚至都可以写源码了。这就是Linux内核和Cisco的网站中包含大量文档...

晨曦之光
2012/04/10
1K
1
2017软考 | 正式的培训课开始之前,我该做些什么?

转眼又到了2017年上半年的软考考试季(5月20日),攻克要塞(公众号ruankao580)与培训结构合作的课程马上就要开始,基于攻克要塞软考团队以往的面授经验,因此,我们就面授课正式开始之前的...

liuyiok
2017/02/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java8新特性之接口

在JDK8以前,我们定义接口类中,方法都是抽象的,并且不能存在静态方法。所有的方法命名规则基本上都是 public [返回类型] [方法名](参数params) throws [异常类型] {}。 JDK8为接口的定义带...

developlee的潇洒人生
42分钟前
0
0
aop + annotation 实现统一日志记录

aop + annotation 实现统一日志记录 在开发中,我们可能需要记录异常日志。由于异常比较分散,每个 service 方法都可能发生异常,如果我们都去做处理,会出现很多重复编码,也不好维护。这种...

长安一梦
52分钟前
2
0
将博客搬至CSDN

AHUSKY
今天
1
0
Python web框架Django学习(1)

1.Django简介 (1)Python下有许多款不同的 Web 框架。Django是重量级选手中最有代表性的一位。许多成功的网站和APP都基于Django。Django是一个开放源代码的Web应用框架,由Python写成。 (2...

十年磨一剑3344
今天
0
0
Databook-数据之书

Databook-数据之书 用于数据分析的Jupyter Notebooks。 不需购买服务器,快速开始自己的数据分析过程。 源码:https://github.com/openthings/databook 作者:openthings,https://github.co...

openthings
今天
5
0
Python PIPEs

https://www.python-course.eu/pipes.php https://www.tutorialspoint.com/python/os_pipe.htm

zungyiu
今天
1
0
gRPC学习笔记

gRPC编程流程 1. proto文件定义 proto文件用于定义需要通过gRPC生成的接口,可以理解为接口定义文档 2. 通过构建工具生成服务基类代码-Maven或Gradle 3. 服务端开发 服务端实现类须实现通过构...

OSC_fly
今天
0
0
Docker Mac (三) Dockerfile 及命令

Dockerfile 最近学习docker的时候,遇到一件怪事,关于docker镜像可能会被破坏,还不知道它会有此措施 所以需要了解构建Dockerfile的正确方法 Dockerfile是由一系列命令和参数构成的脚本,这些命...

___大侠
今天
0
0
Android Studio+NDK+Cmake 移植FFmpeg-4.0.2命令行工具

一、编译 参考大神的帖子,亲测一次编译成功:https://blog.csdn.net/bobcat_kay/article/details/80889398 鉴于以前查文档的经验,这里附上编写例子的时间:2018年7月22日 我用的是ubantu,...

她叫我小渝
今天
0
0
mysql创建数据库

登录MYSQL mysql -u root -p 脚本创建数据库WeChat,并制定默认的字符集是utf8mb4。 CREATE DATABASE Wechat DEFAULT CHARSET utf8mb4 COLLATE utf8mb4_general_ci; 授权 grant all......

niithub
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部