Разбираюсь с алгоритмами и оценкой их сложности. В нескольких примерах заметил момент в связи, с которым и возник следующий вопрос. Приведу абстрактный пример.
Условно задача решается с помощью цикла:
function f2() {
const array = Array(100).fill(null);
return array.reduce((accumulator, currentValue) => {
return accumulator;
}, []);
}
Как я понимаю, это линейная сложность алгоритма O(n).
Если задача решается с помощью цикла и в него вложен ещё один цикл:
function f2() {
const array = Array(100).fill(null);
for (let i = 0; i < array.length; i++) {
for (let j = i + 1; j < array.length; j++) {
}
}
}
То здесь сложность O(n2)
Вопрос насчёт третьего случая, если задача решается, например, с помощью циклов, которые идут друг за другом:
function f3() {
const array = Array(100).fill(null);
return array.reduce((accumulator, currentValue) => {
return accumulator;
}, []);
}
В примерах, это тоже это тоже линейная сложность алгоритма O(n).
Но это же не одно и тоже, что и в первом примере выше.
