离线索引和在线查询的复杂度对比

作者: 皮皮杂谈 | 来源:发表于2019-06-27 08:24 被阅读14次

算法的复杂度，主要是从系统执行时间和所需要占用的存储空间两个方面来衡量，分别称为时间复杂度和空间复杂度。那么，离线索引和在线查询的复杂度对比情况如何呢？

离线索引阶段的时间复杂度主要取决于建立索引的文档数量n，以及每篇文档的长度（即单词数量，最差情况为1）.如果两者都快速增长，那么建立索引的时间会呈现指数级增加。

离线索引的时间和空间复杂度都要远远高于在线查询时的复杂度。

在线查询的时间复杂度主要取决于查询关键词的数量k，以及每个关键词命中的文档（最差情况是n）。所以短查询相对于长查询会更快，而包含生僻词的查询也会更快。

随着分析经验的积累，我们会发现时间和空间复杂度往往是可以相互转换的，然后根据实践应用的需求来做平衡。

最后需要注意的是，这里的时间和空间复杂度只是一种理论上的预估，是根据计算的操作次数，或者是存储单元的数量来统计的。它们假设不同的算法在被衡量的时候都处于同等的环境下，因而不会涉及具体的技术实现和软硬件环境，这和实际的性能指标是有区别的。

无论如何，这种理论上的评估让我们对系统的表现在设计初期就有了大致的了解，提供了方向性的指导。

网友评论

本文标题：离线索引和在线查询的复杂度对比

本文链接：https://www.haomeiwen.com/subject/ffzkcctx.html

离线索引和在线查询的复杂度对比