Большой O линейного поиска массива фиксированного размера

Question

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

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

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

Answer 1

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

Answer 2

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