Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI2 апр. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Что такое оценка сложности O(n)
Введение
Big O notation (O-нотация) — это способ описания того, как алгоритм масштабируется при увеличении размера входных данных. О(n) — это линейная сложность, то есть когда время выполнения растёт пропорционально размеру входных данных.
Основная концепция
O(n) означает: при n элементах алгоритм выполнит примерно n операций
Примеры:
- 10 элементов → 10 операций
- 100 элементов → 100 операций
- 1000 элементов → 1000 операций
- n элементов → n операций
Визуализация
Время выполнения
|
| O(n²) ___/
| /
| / O(n)
| / O(log n)
|_/___________
Размер входных данных
О(n) — это прямая линия, растущая линейно
Примеры O(n) алгоритмов
Пример 1: Простой поиск в массиве
// ✅ O(n) сложность
function findElement(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i; // Нашли элемент
}
}
return -1; // Не нашли
}
const numbers = [1, 2, 3, 4, 5];
console.log(findElement(numbers, 3)); // Операций: ~3
const bigArray = new Array(1000).fill(0).map((_, i) => i);
console.log(findElement(bigArray, 500)); // Операций: ~500
Анализ:
- При массиве из 5 элементов: максимум 5 операций
- При массиве из 1000 элементов: максимум 1000 операций
- Время растёт линейно с размером массива → O(n)
Пример 2: Суммирование всех элементов
// ✅ O(n) сложность
function sumArray(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i]; // Одна операция за элемент
}
return sum;
}
const arr = [1, 2, 3, 4, 5];
console.log(sumArray(arr)); // Операций: 5
// Даже если массив содержит 1 миллион элементов,
// алгоритм просто будет выполнять 1 миллион простых операций
Пример 3: Фильтрация массива
// ✅ O(n) сложность
function filterEvenNumbers(arr) {
const result = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] % 2 === 0) {
result.push(arr[i]); // Одна операция за элемент
}
}
return result;
}
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(filterEvenNumbers(numbers)); // Операций: 10
Пример 4: Методы массивов в JavaScript
// ✅ O(n) сложность
const arr = [1, 2, 3, 4, 5];
// forEach — проходит по каждому элементу
arr.forEach(item => console.log(item)); // O(n)
// map — трансформирует каждый элемент
const doubled = arr.map(x => x * 2); // O(n)
// filter — проверяет каждый элемент
const evens = arr.filter(x => x % 2 === 0); // O(n)
// find — в худшем случае проверяет все элементы
const found = arr.find(x => x === 3); // O(n)
// includes — в худшем случае проверяет все элементы
const hasThree = arr.includes(3); // O(n)
Сравнение с другими сложностями
O(1) - Константная: 1 операция
└─ Обращение к элементу массива по индексу: arr[5]
└─ Получение размера массива: arr.length
O(log n) - Логарифмическая: log n операций
└─ Бинарный поиск в отсортированном массиве
└─ Поиск в BST (Binary Search Tree)
O(n) - Линейная: n операций
└─ Поиск элемента в неотсортированном массиве
└─ Сумма всех элементов
└─ Фильтрация массива
O(n log n) - Линейно-логарифмическая: n log n операций
└─ Сортировка (Merge Sort, Quick Sort)
O(n²) - Квадратичная: n² операций
└─ Вложенные циклы
└─ Сортировка пузырьком (Bubble Sort)
└─ Поиск дубликатов наивным способом
O(2^n) - Экспоненциальная: 2^n операций
└─ Перебор всех подмножеств
└─ Рекурсивный Фибоначчи
O(n!) - Факториальная: n! операций
└─ Генерация всех перестановок
Практический пример: сравнение сложностей
// ❌ O(n²) - МЕДЛЕННО
function findDuplicates_O_n2(arr) {
const duplicates = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
duplicates.push(arr[i]);
}
}
}
return duplicates;
}
// Массив из 100 элементов: 100 * 100 = 10,000 операций
// Массив из 1000 элементов: 1000 * 1000 = 1,000,000 операций
// ✅ O(n) - БЫСТРО
function findDuplicates_O_n(arr) {
const seen = new Set();
const duplicates = [];
for (let i = 0; i < arr.length; i++) {
if (seen.has(arr[i])) {
duplicates.push(arr[i]);
}
seen.add(arr[i]);
}
return duplicates;
}
// Массив из 100 элементов: ~100 операций
// Массив из 1000 элементов: ~1000 операций
// Реальный тест производительности
const largeArray = Array.from({ length: 10000 }, () => Math.floor(Math.random() * 100));
console.time('O(n²)');
findDuplicates_O_n2(largeArray);
console.timeEnd('O(n²)'); // ~1000ms или больше
console.time('O(n)');
findDuplicates_O_n(largeArray);
console.timeEnd('O(n)'); // ~1ms
O(n) в контексте Frontend разработки
Рендер списков
// ✅ O(n) сложность — каждый элемент рендерится один раз
function QuestionsList({ questions }: { questions: Question[] }) {
return (
<ul>
{questions.map(question => (
<li key={question.id}>
<h3>{question.title}</h3>
<p>{question.text}</p>
</li>
))}
</ul>
);
}
// Если questions имеет 100 элементов → 100 LI элементов
// Если questions имеет 1000 элементов → 1000 LI элементов
Фильтрация и поиск
// ✅ O(n) сложность
const handleSearch = (searchTerm: string) => {
const filtered = questions.filter(q =>
q.title.toLowerCase().includes(searchTerm.toLowerCase())
);
setFilteredQuestions(filtered);
};
// Для массива из 10,000 вопросов: ~10,000 операций
Сортировка
// ❌ O(n²) - неэффективно для больших массивов
const sortBubble = (arr) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
};
// ✅ O(n log n) - намного быстрее
const sortQuestions = (questions: Question[]): Question[] => {
return [...questions].sort((a, b) =>
a.difficulty.localeCompare(b.difficulty)
);
};
Важные моменты
1. Big O описывает худший случай
function findInArray(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// Лучший случай: O(1) — элемент на первой позиции
// Средний случай: O(n/2) → обычно говорим O(n)
// Худший случай: O(n) — элемента нет или он в конце
// Big O обычно считает ХУДШИЙ случай
2. Константы игнорируются в Big O
// ❌ Это неправильное обозначение
function processArray(arr) {
for (let i = 0; i < arr.length; i++) console.log(arr[i]);
for (let i = 0; i < arr.length; i++) console.log(arr[i]);
}
// Это O(2n), но мы говорим O(n)
// ✅ Правильно
// O(2n) = O(n) — константы отбрасываются
// O(n + 1000) = O(n)
// O(3n² + 2n + 1) = O(n²) — считаем доминирующий член
3. O(n) лучше, чем O(n²), но хуже, чем O(1) или O(log n)
Быстрое → Медленное
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
Как анализировать сложность
// 1. Считаем циклы
for (let i = 0; i < n; i++) { // Цикл n раз
console.log(i); // O(1) операция
}
// Результат: O(n)
// 2. Вложенные циклы
for (let i = 0; i < n; i++) { // n раз
for (let j = 0; j < n; j++) { // n раз
console.log(i, j); // O(1) операция
}
}
// Результат: O(n * n) = O(n²)
// 3. Последовательные циклы (складываются)
for (let i = 0; i < n; i++) console.log(i); // O(n)
for (let i = 0; i < n; i++) console.log(i); // O(n)
// Результат: O(n + n) = O(n) — константы отбрасываются
Заключение
O(n) означает:
- Линейная сложность
- Время выполнения растёт пропорционально размеру входных данных
- Часто встречается в реальных приложениях
- Считается приемлемой сложностью для большинства задач
Когда встречается O(n) в frontend:
- Поиск элемента в списке
- Фильтрация и трансформация массивов (map, filter, forEach)
- Рендер списков компонентов
- Работа с API ответами
Памятка:
- O(1) — самое быстрое
- O(n) — хорошо для большинства случаев
- O(n²) и выше — старайся избегать для больших данных