Порядок сложности стандартных функций lib

Question

Извините, если это глупый вопрос, но ...

Порядок сложности этого кода 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)?

Как узнать для уверен , каким будет порядок сложности любой стандартной функции?

Answer 1

Да, это должно быть не менее O (n) по дизайну - он получает адрес первого символа и должен найти нулевой символ путем сканирования вдоль строки, и он может сделать это толькопродвигаясь и проверяя каждый символ.

Answer 2

Да, strlen - это O (n), но в этом конкретном примере (со строковым литералом) хороший оптимизатор может заменить strlen(buf) на sizeof(buf).Некоторые компиляторы делают.

Answer 3

Сложность некоторых функций определена в стандарте. Другие, в том числе унаследованные от C, не делают. Тем не менее, вы не можете полагаться ни на что, кроме качества реализации, чтобы поддерживать его на минимальном уровне.