Один проход по данным
O(n) означает линейное время: объём работы растёт вместе с размером входных данных. Вдвое больше элементов — вдвое больше шагов.
В TypeScript линейное время обычно выглядит как один цикл for по массиву или по Map. Любой алгоритм, который обязан хотя бы посмотреть на каждый элемент — суммирование, подсчёт, поиск в неотсортированном массиве — не может работать быстрее, чем O(n).
Линейная сложность — это хорошо. Миллионы элементов не проблема для одного прохода.
Линейный поиск
Если массив не отсортирован, единственный способ найти значение — проверять элементы один за другим, с самого начала. Это линейный поиск.
В худшем случае — значение последнее или его вообще нет — цикл посетит все n элементов. Именно этот худший случай и описывает O(n).
Найти значение и его позицию
Цикл проверяет "one", "two", "three", прежде чем дойти до "four" — 4 шага для совпадения по индексу 3. break останавливает цикл, как только значение найдено.
Вывод: программа на TypeScript и захваченный вывод
const words = ["one", "two", "three", "four", "five"]
let steps = 0
for (let i = 0; i < words.length; i++) {
steps++
if (words[i] === "four") {
console.log("найдено по индексу", i, "— число шагов:", steps)
break
}
}
Посещение каждого элемента
Многие повседневные задачи — это один проход по всему массиву: сложить все значения, запомнить самое большое из встреченных, посчитать элементы, проходящие проверку. Каждый элемент затрагивается ровно один раз, поэтому все они O(n).
Два или три таких прохода подряд всё равно остаются линейными — O(2n) и O(3n) сводятся к O(n).
Сложить все элементы
Цикл добавляет каждый элемент к sum. 8 элементов, 8 сложений — классическая форма одного прохода.
Вывод: программа на TypeScript и захваченный вывод
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let sum = 0
for (const n of nums) {
sum += n
}
console.log("сумма", nums.length, "элементов:", sum)
Найти наибольшее значение
biggest начинается с первого элемента; каждый следующий элемент, который больше, заменяет его. После одного прохода остаётся наибольшее значение — 9.
Вывод: программа на TypeScript и захваченный вывод
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let biggest = nums[0]
for (let i = 1; i < nums.length; i++) {
if (nums[i] > biggest) {
biggest = nums[i]
}
}
console.log("наибольшее значение:", biggest)
Посчитать совпадения
Цикл проверяет каждое слово условием w.length > 3 и считает подходящие. Три слова длиннее 3 букв.
Вывод: программа на TypeScript и захваченный вывод
const words = ["one", "two", "three", "four", "five"]
let count = 0
for (const w of words) {
if (w.length > 3) {
count++
}
}
console.log("слов длиннее 3 букв:", count)