Блог

const a = Array.apply(null, Array(50)).map((x, i) => i);

Этот массив никогда не будет изменен, он всегда будет содержать 50 элементов.

Будет a.includes(x) (линейный поиск) быть O (n) ИЛИ O (50) ИЛИ технически O (50), но мы называем это O (n)

Это не может быть O (N), потому что N подразумевает, что существует определенная переменная, влияющая на время выполнения. Поскольку массив всегда состоит из 50 элементов, он всегда будет проходить цикл 50 раз вместо переменного количества раз — так что эта функция равна O (50), которую мы обычно упрощаем до вызова O(1), который представляет все функции с постоянным временем.

Big-O характеризует функции. Итак, ответ заключается в том, что вы можете выбирать. Если вы определяете функцию, которую пытаетесь охарактеризовать, как что-то вроде «число сравнений в наихудшем случае как функцию от n, количества элементов», то ответом будет O (n). В вашем случае n оказывается равным 50, но если кто-то другой решил ту же проблему для разных значений n, в худшем случае время выполнения будет линейно меняться в зависимости от размера ввода. Если вы определяете это как «количество сравнений для поиска в массиве фиксированной длины», то ответом будет O (1). O(50) — это точно такой же набор функций, что и O(1).