Big-O PHP массивов
Прочитав ответы на List of Big-O для функций PHP, я немного удивился.
В ответе Кендалла Хопкинса говорится, что поиск php - это O(n) для больших массивов и постоянное время (означает O(1)?!) Для маленьких. Он разместил изображение, содержащее график, который показывает время, которое занимает постоянное количество поисков (1 миллион) в зависимости от размера массива. Он начинается почти вертикально, а затем сплющивается.
Из того, что я узнал, постоянное время означает, что время не зависит от элементов массива, что означает горизонтальный график, а не вертикаль. Я думаю, что его график больше похож на O(log n), который соответствует комментариям о том, что PHP реализует рекурсивные хеш-таблицы.
Я провел собственное тестирование (используя его скрипт), и график получился почти таким же (PHP 5.3.23).
Поскольку это лучший ответ, я немного напуган. Можете ли вы сказать мне, если я все это неправильно понимаю? Если так, пожалуйста, помогите мне.
В любом случае: @Kendall Hopkins Спасибо за ваш отличный ответ!
1 ответ
Вы правы, когда говорите, что утверждение Кендалла Хопкинса сбивает с толку / неверно (хотя остальная часть его поста - довольно крутая ссылка для сравнения).
Сказать, что алгоритм является O(1) для небольших входных данных, является довольно бессмысленным утверждением. Сказать, что алгоритм равен O(1), означает, что время выполнения всегда будет меньше константы. Поэтому, если мы ограничим наше входное пространство конечным набором (то есть "маленькими" входами), тогда любой алгоритм будет иметь значение O(1), потому что мы можем просто взять самое длинное время работы из этого набора в качестве нашей константы.
Он имеет в виду, что для начального диапазона входных данных увеличение размера массива будет мало влиять на время работы массива.
Если вы хотите узнать больше о нотации big-O, то [ http://en.wikipedia.org/wiki/Analysis_of_algorithms wikipedia page] является отличной отправной точкой.