{"type":"doc","content":[{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"Короткий ответ"}]},{"type":"paragraph","content":[{"type":"text","text":"Оценка по порядку роста — это способ описать, как время работы или объём памяти алгоритма увеличиваются при росте размера входа n. Обычно используется асимптотическая нотация O(·): мы отбрасываем константы и младшие члены и оставляем доминирующий вклад, например O(n), O(n log n), O(n²)."}]},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"Подробное объяснение"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Что такое порядок роста и зачем он нужен"}]},{"type":"paragraph","content":[{"type":"text","text":"Порядок роста описывает, как быстро растут ресурсы (время, память) алгоритма при увеличении размера входа n. Он позволяет сравнивать алгоритмы абстрагируясь от конкретной машины, языка и оптимизаций, концентрируясь на том, что важнее всего при больших n."}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Сосредотачивается на доминирующем члене: O(n + 5) → O(n)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Игнорирует константные множители: O(3n) → O(n)."}]}]}]},{"type":"blockquote","content":[{"type":"paragraph","content":[{"type":"text","text":"Главная идея: как меняется масштаб времени/памяти при росте n в разы, а не точное число операций."}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Основные нотации"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(g(n)) — верхняя граница по порядку роста: алгоритм не хуже, чем g(n) с точностью до константы при больших n."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Θ(g(n)) — точная по порядку роста: и верхняя, и нижняя границы совпадают (асимптотически такой же рост)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Ω(g(n)) — нижняя граница: алгоритм не лучше, чем g(n) по порядку роста."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"o(g(n)) — растёт строго медленнее, чем g(n). ω(g(n)) — растёт строго быстрее."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Амортизированная сложность — средняя стоимость операции по длинной последовательности вызовов (важно для динамических структур данных)."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Что именно оцениваем"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Время: количество элементарных шагов (итерации, сравнения, присваивания и т. п.)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Память: дополнительная память сверх входных данных (стек рекурсии, временные структуры)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Случай: худший (worst-case), средний (average-case), лучший (best-case). На собеседованиях по умолчанию — худший, если не оговорено иное."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Практические правила оценки кода"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Последовательные участки кода: берём максимум из сложностей, а не сумму, если они зависят от одинакового n (O(n) + O(n²) → O(n²))."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Один цикл по n элементам → O(n). Шаги цикла с делением/умножением индекса (i *= 2) → O(log n)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Вложенные независимые циклы → перемножаем (внешний n, внутренний n → O(n²)). Последовательные циклы по одному и тому же массиву → O(n) + O(n) → O(n)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Условные ветки: берём максимум из веток по порядку роста (наихудший сценарий)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Рекурсия: оцениваем количество вызовов и работу на уровень; часто помогает правило разделяй-и-властвуй (T(n) ≈ a·T(n/b) + f(n)). Примеры: бинарный поиск → O(log n), сортировка слиянием → O(n log n)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Определяйте, что такое n: длина массива, число узлов в дереве, число вершин/рёбер в графе и т. д. От этого зависит оценка."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Примеры кода и их порядок роста (JS)"}]},{"type":"paragraph","content":[{"type":"text","text":"Линейный проход по массиву — O(n) по времени, O(1) по памяти:"}]},{"type":"codeBlock","content":[{"type":"text","text":"function sum(arr) {\n let s = 0;\n for (let i = 0; i < arr.length; i++) {\n s += arr[i];\n }\n return s;\n}"}]},{"type":"paragraph","content":[{"type":"text","text":"Вложенные циклы — O(n²) по времени:"}]},{"type":"codeBlock","content":[{"type":"text","text":"function hasDuplicates(arr) {\n for (let i = 0; i < arr.length; i++) {\n for (let j = i + 1; j < arr.length; j++) {\n if (arr[i] === arr[j]) return true;\n }\n }\n return false;\n}"}]},{"type":"paragraph","content":[{"type":"text","text":"Бинарный поиск по отсортированному массиву — O(log n) по времени:"}]},{"type":"codeBlock","content":[{"type":"text","text":"function binarySearch(arr, x) {\n let l = 0, r = arr.length - 1;\n while (l <= r) {\n const m = (l + r) >> 1;\n if (arr[m] === x) return m;\n if (arr[m] < x) l = m + 1; else r = m - 1;\n }\n return -1;\n}"}]},{"type":"paragraph","content":[{"type":"text","text":"Слияние двух отсортированных массивов — O(n + m) по времени, O(n + m) по памяти (для результата):"}]},{"type":"codeBlock","content":[{"type":"text","text":"function merge(a, b) {\n const res = [];\n let i = 0, j = 0;\n while (i < a.length && j < b.length) {\n if (a[i] <= b[j]) res.push(a[i++]);\n else res.push(b[j++]);\n }\n while (i < a.length) res.push(a[i++]);\n while (j < b.length) res.push(b[j++]);\n return res;\n}"}]},{"type":"paragraph","content":[{"type":"text","text":"Сортировка слиянием — O(n log n) по времени, O(n) дополнительной памяти:"}]},{"type":"codeBlock","content":[{"type":"text","text":"function mergeSort(arr) {\n if (arr.length <= 1) return arr;\n const mid = arr.length >> 1;\n const left = mergeSort(arr.slice(0, mid));\n const right = mergeSort(arr.slice(mid));\n // Слияние — как в примере выше\n const res = [];\n let i = 0, j = 0;\n while (i < left.length && j < right.length) {\n if (left[i] <= right[j]) res.push(left[i++]);\n else res.push(right[j++]);\n }\n while (i < left.length) res.push(left[i++]);\n while (j < right.length) res.push(right[j++]);\n return res;\n}"}]},{"type":"paragraph","content":[{"type":"text","text":"Амортизированная сложность push в динамический массив — O(1) в среднем, иногда O(n) при редком расширении:"}]},{"type":"codeBlock","content":[{"type":"text","text":"class DynArray {\n constructor() {\n this.a = new Array(1);\n this.n = 0;\n }\n push(x) {\n if (this.n === this.a.length) {\n const b = new Array(this.a.length * 2);\n for (let i = 0; i < this.n; i++) b[i] = this.a[i];\n this.a = b; // редкая, но дорогая операция: O(n)\n }\n this.a[this.n++] = x; // обычно O(1)\n }\n}"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Типичные порядки роста и интуиция"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(1) — константное: доступ по индексу в массиве, push в конец динамического массива (амортиз.)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(log n) — делим пополам: бинарный поиск, операции в сбалансированных деревьях поиска."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n) — линейный проход: проверка условия для каждого элемента массива/списка/узла."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n log n) — сортировки сравнениями, многие алгоритмы divide & conquer (слияние, быстрая сортировка в среднем)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n²) — двойные вложенные циклы: сравнение всех со всеми, наивные алгоритмы динамики без оптимизаций."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(2^n), O(n!) — полный перебор, комбинаторные задачи без оптимизаций/срезов."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Частые ошибки и тонкости"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Путаница в определении n: для графов важно различать |V| (вершины) и |E| (рёбра); для строк — длину в символах; для чисел — количество битов, а не величину числа."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Игнорирование памяти: рекурсивные алгоритмы часто требуют O(depth) стека; некоторые методы сортировки требуют O(n) дополнительной памяти."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Слишком буквальное восприятие констант: асимптотика игнорирует константы, но на малых n они могут быть важны на практике. На собеседовании — обсуждайте компромиссы."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Как отвечать на собеседовании"}]},{"type":"orderedList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Скажите, что считаете за n (размер входа) и какой случай рассматриваете (обычно худший)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Разберите код на блоки: последовательные части, циклы, ветвления, рекурсия; примените правила сложения/умножения/максимума."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Назовите временную и пространственную сложность; при необходимости — амортизированную."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Сравните альтернативы и укажите узкое место (например, «бутылочное горлышко — вложенный цикл O(n²)»)."}]}]}]}]}

Что означает “оценка по порядку роста”?

Комментарии