Алгоритмическая сложность php-функций

Question

[andymitrich]

Доброго времени суток, коллеги. Не встречали ли вы где-нибудь на просторах интернета описание функций php с точки зрения алгоритмической сложности?

Comments

[sl4mmer]

Какие именно вас функции интересуют?

Если вы про функции из SPL — то в чем проблема оценить сложность, исходники то доступны =)

[andymitrich]

Ну вот этого я и пытаюсь избежать :) Хотелось бы на все готовенькое.

Answer 1

[Сергей Протько]

stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions

Comments

[Сергей Протько]

опять же тут приведена информация только для функций для работы с массивами. Причем сложность различается для некоторых функций в зависимости от того что вы используете (обычный массив, объект имплементящий ArrayAccess или же SplFixedArray и т.д. Информация почти по всем функциям так или иначе есть, но она сильно разрознена. В самой документации сложность алгоритмов описана только для вещей вроде similar_text и т.д. Именно полный список вы вряд-ли найдете.

[andymitrich]

В любом случае, большущее вам спасибо. Постараюсь собрать все вместе.

Answer 2

[popov]

Попытайтесь определить сложность на экспериментах (по крайней мере, этот метод приходит одним из первых на ум), подавая разные данные на вход, усредняя время выполнения функции и строя графики зависимости среднего времени от длины входных данных. Мне кажется, это может быть интересным, а хорошо сделанного материала может хватить на статью в рецензируемом журнале или на Хабре.

Опять же, эксперименты требуют довольно большого времени, иногда проще оценивать код.

Comments

[andymitrich]

Ну по большому счету можно скомпоновать теоретический подход, путем нахождения асимптотики, с эмпирическим, выполняя эксперименты и проводя соответсвующие замеры.

Answer 3

[Николай Васильчук]

В каком-то тестовом задании мне присылали вопрос об алгоритмической сложности функции strlen. В исходниках нашел довольно быстро.

Comments

[andymitrich]

Ну вопросов о сложности strlen не поднимал только ленивый :)