标准库函数的复杂度顺序
抱歉，如果这是一个愚蠢的问题，但是...
这段代码的复杂度顺序是 O(n):
char buf[] = "hello world";
size_t length = strlen(buf);
for(size_t i = 0; i < length; i++)
{
//do stuff
}
并且这段代码是 O(n^2):
char buf[] = "hello world";
for(size_t i = 0; i < strlen(buf); i++)
{
//do stuff
}
因为 strlen 是 O(n)。
但谁说strlen是O(n)，标准里有定义吗，一定是O(n)吗？
我如何才能确定知道任何标准函数的复杂度是多少？
Sorry if this is a stupid question, but...
The order of Complexity of this code is O(n):
char buf[] = "hello world";
size_t length = strlen(buf);
for(size_t i = 0; i < length; i++)
{
//do stuff
}
and this code is O(n^2):
char buf[] = "hello world";
for(size_t i = 0; i < strlen(buf); i++)
{
//do stuff
}
because strlen is O(n).
But who says that strlen is O(n), is it defined in the standard, does it have to be O(n)?
How can I know for sure what the Order of Complexity of any standard function is going to be?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的，设计必须至少为 O(n) - 它接收的地址第一个字符，必须通过扫描字符串来找到空字符，并且只能通过前进并检查每个字符来做到这一点。
Yes, it has to be at least O(n) by design - it receives the address of the first character and has to find the null character by scanning along the string and it can only do so by advancing and checking each character.
标准中定义了某些函数的复杂性。其他的，包括那些从 C 继承的，则没有。对于这些，除了实施质量之外，您不能依靠任何其他东西来将其保持在最低限度。
Some functions have their complexity defined in the standard. Others, included those inherited from C, don't. For those, you can't rely on anything else than quality of implementation to keep it at the minimum.
是的，strlen 的复杂度为 O(n)，但在这个特定示例（使用字符串文字）中，好的优化器可以用
sizeof(buf)替换strlen(buf)。有些编译器会这样做。Yes, strlen is O(n), but in this particular example (with a string literal) a good optimizer can replace
strlen(buf)withsizeof(buf). Some compilers do.