最近，我被要求创建一个程序来查找文本片段中的最佳匹配。我已经成功编写了这个程序，但我确实对其时间复杂度有疑问。
问题定义如下。
给定一个查询，查找文档中出现的查询词并突出显示最佳标记。
我的程序花费的时间
O(m + n + p)
here
m = 文档长度（以字符为单位）
n = 查询的长度（以字符为单位）
p = 文档中的总匹配数
在这种情况下，最大的术语始终是“m”，因为在大多数情况下，文档将比查询本身更大。
我可以安全地推断出我的程序的时间复杂度是 O(m) 吗？
不，你不能。根据大 O 表示法你的职能m是算法运行实际时间的上限（如果有一个常数）M比如实际时间总是小于或等于M*m。以文档大小为零（空文档）但有人使用正数字符查询它的情况为例。在这种情况下的上限将是0（加上一个常量），但程序运行的实际时间可能比这个长。所以你的程序不能说是O(m).
换句话说，“大多数情况”是不够的：您必须证明您的算法将在该上限内执行all cases.
Update:同样可以这样说p: 常识说p总是小于m，但这仅在搜索词不重叠的情况下成立。以文档为例aaaaaa(m=6) 和搜索词a, aa and aaa(n=3)。在本例中，出现了 6 次a, 5 of aa和 4 个aaa, so p = 15。尽管这是一种非常不可能的情况（与空文档相同），但仍然需要您采取p在您的复杂性分析中考虑到。所以你的程序必须被描述为O(m + n + p)正如你最初所说。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
