C ++字符串::找到的复杂性 [英] C++ string::find complexity

问题描述

为什么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 ++字符串::找到的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！