为什么C ++的实施字符串::找到()不使用的 KMP算法(并没有在 O(N + M)),并运行在 O(N * M)?是,在C ++ 0x的修正? 如果当前发现的复杂程度不 O(N * M),那是什么?
PS: 对不起,我的意思是字符串::找到()
等什么算法在gcc中实现?是KMP?如果没有,为什么? 我测试过这一点,运行时间表明,它在 O(N * M)运行
解决方案为什么C ++的执行字符串:: SUBSTR()不使用KMP算法(并且不为O(N + M)运行),并运行在O(N * M)?
我假定你的意思找到(),而不是 SUBSTR()这并不需要搜索和应线性时间运行(并且仅因为它具有的结果复制到一个新的字符串)。
C ++标准没有规定实施细则,并只规定在某些情况下,复杂性要求。在的std ::串唯一的复杂性要求操作是尺寸(), MAX_SIZE( ),运算符[] ,交换(), c_str ()和数据()都是恒定的时间。在别的复杂性依赖于谁实现了您正在使用的库所做的选择。
选购了类似KMP一个简单的搜索最有可能的原因是为了避免需要额外的存储空间。除非要查找的字符串很长,而且搜索的字符串包含了很多部分匹配的,所花费的时间分配和释放,将可能比额外的复杂性成本等等。
时,在C纠正++ 0x中?
没有,C ++ 11中不添加任何复杂性要求的std ::字符串,当然不会增加任何强制性的实施细则。
如果当前SUBSTR的复杂性不是O(N * M),那是什么?
这是最坏情况下的复杂性,如果要搜索的字符串中包含了很多长的部分比赛。如果角色有一个合理的均匀分布,那么平均的复杂性将接近 O(N)。因此,通过提供更好的最坏情况复杂选择算法,你可能赚更多的典型案例要慢得多。
Why the c++'s implemented string::find() doesn't use the KMP algorithm (and doesn't run in O(N + M)) and runs in O(N * M)? Is that corrected in C++0x? If the complexity of current find is not O(N * M), what is that?
PS: Sorry I mean string::find()
so what algorithm is implemented in gcc? is that KMP? if not, why? I've tested that and the running time shows that it runs in O(N * M)
解决方案Why the c++'s implemented string::substr() doesn't use the KMP algorithm (and doesn't run in O(N + M)) and runs in O(N * M)?
I assume you mean find(), rather than substr() which doesn't need to search and should run in linear time (and only because it has to copy the result into a new string).
The C++ standard doesn't specify implementation details, and only specifies complexity requirements in some cases. The only complexity requirements on std::string operations are that size(), max_size(), operator[], swap(), c_str() and data() are all constant time. The complexity of anything else depends on the choices made by whoever implemented the library you're using.
The most likely reason for choosing a simple search over something like KMP is to avoid needing extra storage. Unless the string to be found is very long, and the string to search contains a lot of partial matches, the time taken to allocate and free that would likely be much more than the cost of the extra complexity.
Is that corrected in c++0x?
No, C++11 doesn't add any complexity requirements to std::string, and certainly doesn't add any mandatory implementation details.
If the complexity of current substr is not O(N * M), what is that?
That's the worst-case complexity, when the string to search contains a lot of long partial matches. If the characters have a reasonably uniform distribution, then the average complexity would be closer to O(N). So by choosing an algorithm with better worst-case complexity, you may well make more typical cases much slower.
更多推荐
C ++字符串::找到的复杂性
发布评论