我最近被要求创建一个程序来查找文本片段中的最佳匹配。我已经成功编写了这个程序，但我对它的时间复杂度有疑问。
问题定义如下。
给定查询，在文档中查找查询词的出现并突出显示最佳标记。
我的程序花费的时间
O(m + n + p)
这里
m = 文档长度（以字符为单位）
n = 查询的字符长度
p = 文档中的总匹配数
在这种情况下，最大的术语总是“m”，因为在大多数情况下，文档会比查询本身大。
我可以安全地推断出我的程序的时间复杂度是 O(m) 吗？
问问题
3480 次
2 回答
4
不，你不能。根据Big-O 表示法，您的函数m是算法运行实际时间的上限，如果有一个常数M，例如实时时间总是小于或等于M*m. 以文档大小为零（一个空文档）但有人用正数字符查询它的情况为例。在这种情况下，上限将是0（加上一个常数），但程序运行的实际时间可能会大于这个值。所以你的程序不能说是O(m)。
换句话说，“大多数情况”是不够的：您必须证明您的算法在所有情况下都将在该上限内执行。
更新：同样可以这样说p：常识说p总是小于m，但只有当搜索词不重叠时才会如此。以文档aaaaaa(m=6) 和搜索词a,aa和aaa(n=3) 为例。在这种情况下，出现 6 次，出现a5次，出现aa4 次aaa，所以p = 15。即使这是一个非常不可能的情况（对于空文档也是如此），您仍然需要p在复杂性分析中考虑到这一点。所以你的程序必须真的O(m + n + p)像你最初所说的那样描述。
于 2012-06-06T23:46:03.503 回答
1
我的程序花费的时间：O(m + n + p) 首先，我完全不相信这是你的程序花费的时间。
您被要求解析查询并在文档中查找单词。这是一个复杂的交叉引用问题，因为您有多个单词中的字符必须以精确的字符序列与随机放置在文档中的相同序列匹配。大多数学生对此进行哈希处理并创建一个 N 平方过程，方法是获取第一个单词并扫描文档以查找该单词的出现，然后对下一个、下一个和下一个执行相同的操作。您需要开发一种交叉引用文档内容和单词的有效方法，否则您将创建一个 N^2 过程。副手，在查询中创建一个单词词典，将文档解析为单词并将它们与要查找的单词词典进行匹配。那将是 mLogn
m = number of words the document
n = number of words in the dictionary you create in an nLogn process.
在我写的一篇文章中提到了你，因为它解决了一个类似但更复杂的单词匹配问题：
http://www.codeproject.com/Tips/882998/Performance-Solving-WonderWord-Puzzle
您的第一个受访者是正确的，同时假设我没有认为您必须在不使用中断的情况下找到字符，但我认为他的 O 表示法是错误的，因为它们是相乘的，而不是相加的，并且 p 是不相关的。
于 2015-03-20T23:07:36.437 回答