Профессиональная коллекция алгоритмов и структур данных с подробными объяснениями, анализом сложности и практическими примерами применения.
O-нотация (Big O Notation) — это математический способ описания того, как время выполнения или использование памяти алгоритма растет с увеличением размера входных данных.
O-нотация помогает:
- Сравнивать алгоритмы по эффективности
- Предсказывать производительность на больших данных
- Выбирать оптимальное решение для конкретной задачи
- Общаться с коллегами на едином языке
Время выполнения не зависит от размера входных данных.
// Пример: доступ к элементу массива по индексу function getFirstElement(arr: number[]): number { return arr[0]; // Всегда выполняется за одно действие }
Характеристики:
- Самый быстрый вариант
- Время: константа
- Память: константа
Примеры:
- Доступ к элементу массива по индексу
- Добавление элемента в конец массива
- Получение размера коллекции
Время выполнения растет логарифмически от размера данных.
// Пример: бинарный поиск function binarySearch(arr: number[], target: number): number { let left = 0; let right = arr.length - 1;
while (left <= right) { const mid = Math.floor((left + right) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }
Характеристики:
- Очень быстрый
- Время: логарифм от n
- Память: обычно O(1)
Примеры:
- Бинарный поиск
- Поиск в сбалансированном бинарном дереве
- Деление пополам (divide and conquer)
Визуализация:
- n = 10 → ~3 операции
- n = 100 → ~7 операций
- n = 1000 → ~10 операций
Время выполнения прямо пропорционально размеру данных.
// Пример: линейный поиск function linearSearch(arr: number[], target: number): number { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; } return -1; }
Характеристики:
- Хорошая производительность
- Время: прямо пропорционально n
- Память: обычно O(1) или O(n)
Примеры:
- Проход по массиву
- Поиск максимума/минимума
- Подсчет элементов
Визуализация:
- n = 10 → 10 операций
- n = 100 → 100 операций
- n = 1000 → 1000 операций
Время выполнения растет как n умноженное на log n. // Пример: эффективные сортировки function mergeSort(arr: number[]): number[] { if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid));
return merge(left, right); }
Характеристики:
- Хорошая производительность для сортировок
- Время: n × log n
- Память: обычно O(n)
Примеры:
- Быстрая сортировка (Quick Sort)
- Сортировка слиянием (Merge Sort)
- Пирамидальная сортировка (Heap Sort)
Визуализация:
- n = 10 → ~33 операции
- n = 100 → ~664 операции
- n = 1000 → ~9966 операций
Время выполнения пропорционально квадрату размера данных.
// Пример: сортировка пузырьком function bubbleSort(arr: number[]): number[] { const result = [...arr]; for (let i = 0; i < result.length; i++) { for (let j = 0; j < result.length - i - 1; j++) { if (result[j] > result[j + 1]) { [result[j], result[j + 1]] = [result[j + 1], result[j]]; } } } return result; }
Характеристики:
- Медленно на больших данных
- Время: квадрат от n
- Память: обычно O(1)
Примеры:
- Сортировка пузырьком
- Сортировка выбором
- Вложенные циклы
Визуализация:
- n = 10 → 100 операций
- n = 100 → 10,000 операций
- n = 1000 → 1,000,000 операций
Время выполнения удваивается с каждым новым элементом.
// Пример: рекурсивный расчет Фибоначчи (неоптимальный) function fibonacciNaive(n: number): number { if (n <= 2) return 1; return fibonacciNaive(n - 1) + fibonacciNaive(n - 2); }
Характеристики:
- Очень медленно
- Время: экспонента от n
- Память: O(n) из-за стека вызовов
Примеры:
- Рекурсивный Фибоначчи без мемоизации
- Генерация всех подмножеств
- Некоторые задачи оптимизации
Визуализация:
- n = 10 → ~1024 операций
- n = 20 → ~1,048,576 операций
- n = 30 → ~1,073,741,824 операций
Время выполнения растет факториально.
Характеристики:
- Крайне медленно
- Время: факториал от n
- Память: обычно O(n)
Примеры:
- Генерация всех перестановок
- Задача коммивояжера (полный перебор)
Визуализация:
- n = 5 → 120 операций
- n = 10 → 3,628,800 операций
- n = 20 → астрономическое число
| Сложность | n=10 | n=100 | n=1000 | Описание |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | Константа |
| O(log n) | ~3 | ~7 | ~10 | Логарифм |
| O(n) | 10 | 100 | 1000 | Линейная |
| O(n log n) | ~33 | ~664 | ~9966 | Линейно-логарифмическая |
| O(n²) | 100 | 10,000 | 1,000,000 | Квадратичная |
| O(2ⁿ) | ~1024 | ~10³⁰ | ~10³⁰⁰ | Экспоненциальная |
| O(n!) | 3,628,800 | ~10¹⁵⁸ | ~10²⁵⁶⁸ | Факториальная |
- Игнорируем константы: O(2n) → O(n)
- Берем доминирующий член: O(n² + n) → O(n²)
- Игнорируем меньшие степени: O(n + log n) → O(n)
Каждый алгоритм находится в отдельной папке и содержит:
README.md— подробное описание алгоритма*.ts— реализация на TypeScript*.test.ts— unit-тесты
- Уровень 1: Базовые алгоритмы (O(n))
- Уровень 2: Простые алгоритмы (O(n log n))
- Уровень 3: Квадратичные сортировки (O(n²))
- Уровень 4: Эффективные сортировки (O(n log n))
- Уровень 5: Структуры данных (O(log n) - O(1))
- Уровень 6: Деревья и графы (O(V + E))
- Уровень 7: Сложные алгоритмы (O(n) - O(2ⁿ))
- Node.js >= 18.0.0
- npm >= 9.0.0
npm install
npm run build### Запуск тестов
npm test### Запуск конкретного алгоритма
npm run test -- basicAlgorithms/linearSearch---
- Выберите интересующий алгоритм из структуры проекта
- Откройте
README.mdв папке алгоритма для подробного объяснения - Изучите реализацию в
*.tsфайле - Запустите тесты для проверки работы
Приветствуются любые улучшения! Пожалуйста:
- Создайте issue для обсуждения изменений
- Сделайте fork проекта
- Создайте feature branch
- Добавьте тесты для новых алгоритмов
- Отправьте pull request