Какую сложность алгоритма мы получаем при суммировании выборки из начал массива?

Question

[MishaXXL]

Есть массив в JavaScript
[1,2,3,4,5,6,7]
При выборке значений через pop(), у нас обход получается O(N)
А если мы будем брать значения с начала, через shift()
Какая тогда сложность алгоритма получается?
Как я понял после каждого shiftу нас по умолчанию происходит полный обход массива заново для его переопределения очередности элементов

И как правильно рассчитать сложность алгоритма под

const arr = [8,24,31,4,5,6,17]
arr.sort()
for(let i = 0; i < arr.length; i++) arr.shift()

Answer 1

[Alexandroppolus]

Каждый shift сдвигает все элементы массива, т.е. один shift - O(N), а весь обход - O(N^2)

не используй его в цикле, если у тебя длинный массив

Comments

[MishaXXL]

Спасибо, а как складывается O(logN) и O(N^2), когда у нас идет сортировка, а после линейное вычисление?

[Даша Циклаури]

MishaXXL, по верхней границе, то есть n^2, степенная функция растет быстрее логарифмической

[MishaXXL]

Даша Циклаури, извиняюсь, может не так понял
for(let i = 0; i < arr.length; i++) arr.shift() -> O(N^2)

и это тоже O(N^2)?

arr.sort()
for(let i = 0; i < arr.length; i++) arr.shift()

Мне казалось, что сортировка должна добавить сложности и нужно суммировать с последующими действиями
Или как это работает?

[Alexandroppolus]

MishaXXL, сортировка здесь O(N * logN), но это всё равно меньше чем O(N^2)

по правилам асимптотики, O(N * logN) + O(N^2) = O(N^2), берется самое жирное слагаемое.

[MishaXXL]

Alexandroppolus, тысяча извинений, если вопрос глупый
Почему не происходит сложение, а выбирается наибольшее значение из всех операций в функции?

Или сложность алгоритма не относится, как к таковой общей функции, а только лишь к самим переборам значений?

Здесь тоже наименьшее sortпроигнорируется при описании сложности алгоритма и будет O(N^2)?
arr.sort().map((item, i, arr) => arr.pop())

[Alexandroppolus]

MishaXXL, https://proglib.io/p/asymptotic-complexity

Здесь тоже наименьшее sortпроигнорируется при описании сложности алгоритма и будет O(N^2)?
arr.sort().map((item, i, arr) => arr.pop())

здесь у нас сортировка за O(N * logN) и map за O(N). Снова берем самое большое, им теперь оказывается O(N * logN)

[MishaXXL]

Alexandroppolus, извиняюсь, случайно поп, а не шифт написал
Тут получается O(2N*LogN)?
arr.sort().map((item, i, arr) => arr.shift())