string.h 中 strncmp 的复杂性

Question

我想知道C库中int strncmp(const char *__s1, const char *__s2, size_t __n)的时间复杂度(string.h).

我必须研究调用 strncmp 数千次的整个程序的复杂性，我不能忽视这种复杂性。
我在哪里可以找到有关 C 库函数复杂性的文档？

Answer 1

标准对复杂度没有要求。这完全取决于实施。但是绝对没有理由期望它会是 O(__n)

之外的任何东西

• 编写一个满足 O(__n) 的实现是微不足道的，所以没有理由怀疑专业人士做出的实际实现会更糟。

• 不可能写出比O(__n)更好的实现，所以这种情况不会发生。

但是如果你想确定，你必须研究你正在使用的特定实现。