Перейти к основному содержимому

Алгоритмы — чек-лист

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Аналитику Тестировщику
Архитектору Инженеру

Загрузка вопросов…

Чек-лист самопроверки​

Общие понятия​

  1. Могу ли я своими словами объяснить, что такое алгоритм?
  2. Понимаю ли я три ключевых свойства алгоритма — дискретность, определённость, конечность?
  3. Могу ли я привести пример алгоритма из повседневной жизни и разбить его на шаги?
  4. Понимаю ли я разницу между алгоритмом и программой?
  5. Могу ли я объяснить, почему алгоритм должен быть детерминированным?

Анализ сложности​

  1. Понимаю ли я, что означает нотация O(f(n))?
  2. Могу ли я отличить временнýю сложность от пространственной?
  3. Знаю ли я, чем отличаются обозначения O, Ω и Θ?
  4. Могу ли я объяснить, почему в асимптотическом анализе игнорируют константы?
  5. Понимаю ли я, что O описывает поведение при стремлении n к бесконечности?

Основные классы сложности​

  1. Могу ли я привести пример алгоритма с константной сложностью O(1)?
  2. Понимаю ли я, почему доступ к элементу массива по индексу — O(1)?
  3. Могу ли я объяснить, как работает бинарный поиск и почему его сложность — O(log n)?
  4. Могу ли я привести пример задачи, которая требует линейного времени O(n)?
  5. Понимаю ли я, почему полный перебор всех пар элементов даёт квадратичную сложность O(n²)?
  6. Знаю ли я, какие алгоритмы имеют сложность O(n log n) и почему это важный порог?
  7. Могу ли я объяснить, почему экспоненциальные алгоритмы O(2^n) непрактичны для больших n?
  8. Знаю ли я, когда возникает O(n³) (например, наивное умножение матриц)?
  9. Могу ли я назвать задачу с O(√n) или O(n!) и объяснить разницу с O(2^n)?

Сортировка и поиск​

  1. Могу ли я описать, как работает сортировка вставками и в каких случаях она эффективна?
  2. Понимаю ли я принцип "разделяй и властвуй" на примере сортировки слиянием?
  3. Знаю ли я, как устроена быстрая сортировка и какие есть стратегии выбора опорного элемента?
  4. Понимаю ли я, почему пирамидальная сортировка гарантирует O(n log n)?
  5. Могу ли я объяснить, в чём разница между сравнительными и несравнительными алгоритмами сортировки?
  6. Знаю ли я, что такое устойчивая сортировка и когда это важно?
  7. Могу ли я реализовать бинарный поиск и объяснить его тонкости (переполнение, зацикливание)?
  8. Понимаю ли я, как искать границы (lower bound, upper bound) с помощью бинарного поиска?
  9. Знаю ли я, зачем нужен самоорганизирующийся поиск и когда он уместен?
  10. Понимаю ли я принцип GIGO и проверку предусловий алгоритма?

Графы и ранжирование​

  1. Могу ли я объяснить разницу между вершиной, ребром и весом?
  2. Понимаю ли я, чем BFS отличается от алгоритма Дейкстры?
  3. Могу ли я словами описать идею PageRank и степенного метода?
  4. Знаю ли я критерий существования эйлерова цикла (чётные степени в связном графе)?
  5. Понимаю ли я разницу между эйлеровым циклом (по рёбрам) и гамильтоновым (по вершинам)?
  6. Могу ли я объяснить, зачем нужна топологическая сортировка DAG зависимостей?
  7. Знаю ли я, что такое минимальный остов и чем отличаются идеи Прима и Краскала?
  8. Знаю ли я, что такое НОД и как работает алгоритм Евклида?

Практическое применение​

  1. Могу ли я определить сложность простого алгоритма, глядя на его код?
  2. Умею ли я находить скрытую квадратичную сложность (например, вызов линейной функции внутри цикла)?
  3. Понимаю ли я, когда выгодно сортировать данные перед поиском, а когда — нет?
  4. Знаю ли я, какие структуры данных обеспечивают O(1) для поиска, а какие — O(log n)?
  5. Могу ли я объяснить, почему хеш-таблица в среднем даёт O(1), но в худшем случае — O(n)?
  6. Понимаю ли я, как локальность данных (cache locality) влияет на реальную производительность?
  7. Знаю ли я, что такое амортизированный анализ и как он применяется к динамическим массивам?

Классы времени выполнения​

  1. Могу ли я объяснить разницу между статической компиляцией, интерпретацией и JIT-компиляцией?
  2. Знаю ли я, какие языки относятся к нативному классу (A), а какие — к управляемому (B)?
  3. Понимаю ли я, какие преимущества даёт управляемая среда выполнения (сборка мусора, безопасность)?
  4. Знаю ли я, какие задачи лучше решать с помощью нативного кода, а какие — с помощью скриптов?
  5. Понимаю ли я, почему современные JavaScript-движки так быстры, несмотря на интерпретацию?

Инструменты и методы​

  1. Умею ли я использовать профилировщик для измерения производительности своего кода?
  2. Знаю ли я, как проводить нагрузочное тестирование для проверки масштабируемости?
  3. Могу ли я объяснить, почему преждевременная оптимизация — это антипаттерн?
  4. Понимаю ли я, как алгоритмическая сложность влияет на проектирование баз данных (индексы, запросы)?
  5. Знаю ли я, как избежать проблемы N+1 при работе с базами данных?

Продвинутые темы​

  1. Понимаю ли я, что такое амортизированная сложность и как она применяется?
  2. Знаю ли я, как работает экспоненциальный поиск в бесконечных последовательностях?
  3. Могу ли я объяснить, почему Timsort эффективен на частично упорядоченных данных?
  4. Понимаю ли я, как факторизовать сложность: например, O(n log n) как комбинация O(n) и O(log n)?
  5. Знаю ли я, какие существуют методы амортизированного анализа (совокупная оценка, потенциал)?
  6. Понимаю ли я, как аппаратная архитектура (кэши, NUMA) влияет на выбор алгоритма?
  7. Могу ли я объяснить, почему некоторые алгоритмы с "худшей" асимптотикой быстрее на малых n?
  8. Знаю ли я, где в стандартных библиотеках моего языка используются гибридные алгоритмы (Introsort, Timsort)?

Практика на Python​

После самопроверки по списку выше закрепите оценку сложности по коду — Big-O — шпаргалка с примерами (вопросы 6–19 в чек-листе выше), затем типовые приёмы готовым кодом — Алгоритмы на Python — ЕГЭ и олимпиадка, Java — консольные задачи или Pascal / Free Pascal — типовые программы — ввод-вывод, сортировка, бинарный поиск; у каждого блока есть разбор и пример входа/выхода.

Последнее обновление
Содержание