Aug 21

C++ String的find()成员函数 不指定

felix021 @ 2008-8-21 14:53 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(11247) | Via 本站原创 | |
摘自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
Tags:
圭寺
2011-1-20 22:28
有点意思,不是太懂。感谢。
find
2008-11-17 14:35
stupid  英文的看不太懂也
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]