Aug
21
C++ String的find()成员函数
摘自boost库的文档:
Currently the library contains only naive implementation of find algorithms with complexity O(n * m) where n is the size of the input sequence and m is the size of the search sequence. There are algorithms with complexity O(n), but for smaller sequence a constant overhead is rather big. For small m < < n (m by magnitude smaller than n) the current implementation provides acceptable efficiency. Even the C++ standard defines the required complexity for search algorithm as O(n * m). It is possible that a future version of library will also contain algorithms with linear complexity as an option。
也就是说string::find()提供的是O(m*n)的效率,不是KMP的O(n),很汗。。。
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
Currently the library contains only naive implementation of find algorithms with complexity O(n * m) where n is the size of the input sequence and m is the size of the search sequence. There are algorithms with complexity O(n), but for smaller sequence a constant overhead is rather big. For small m < < n (m by magnitude smaller than n) the current implementation provides acceptable efficiency. Even the C++ standard defines the required complexity for search algorithm as O(n * m). It is possible that a future version of library will also contain algorithms with linear complexity as an option。
也就是说string::find()提供的是O(m*n)的效率,不是KMP的O(n),很汗。。。
欢迎扫码关注:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
圭寺
2011-1-20 22:28
有点意思,不是太懂。感谢。
find
2008-11-17 14:35
英文的看不太懂也
分页: 1/1 1