{"type":"doc","content":[{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"Короткий ответ"}]},{"type":"paragraph","content":[{"type":"text","text":"Скорость роста функции — это то, как быстро увеличивается значение f(n) при росте n. В анализе алгоритмов её описывают асимптотическими обозначениями (O, Θ, Ω), чтобы сравнивать алгоритмы по порядку роста времени или памяти на больших входах, игнорируя константы и младшие члены."}]},{"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 → ∞. Если для двух функций f(n) и g(n) при достаточно больших n значения f растут не быстрее некоторого постоянного множителя от g, говорят, что f(n) имеет не более быстрый порядок роста, чем g(n). В алгоритмах это позволяет определить, как будет масштабироваться время выполнения или использование памяти при увеличении размера входа n."}]},{"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":"Сравнение альтернатив: выбираем меньший порядок роста (например, n log n лучше, чем n^2)."}]}]},{"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":"O(g(n)) — верхняя оценка (не растёт быстрее, с точностью до константы): f(n) ∈ O(g(n)) если ∃ c > 0, n0: f(n) ≤ c·g(n) для всех n ≥ n0."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Ω(g(n)) — нижняя оценка (не растёт медленнее, с точностью до константы): f(n) ∈ Ω(g(n)) если ∃ c > 0, n0: f(n) ≥ c·g(n) для всех n ≥ n0."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Θ(g(n)) — точный порядок (и верхняя, и нижняя оценка одновременно): f(n) ∈ Θ(g(n)) если f ∈ O(g) и f ∈ Ω(g)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"o(g(n)) — строго медленнее (f/g → 0)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"ω(g(n)) — строго быстрее (f/g → ∞)."}]}]}]},{"type":"blockquote","content":[{"type":"paragraph","content":[{"type":"text","text":"Важно: базис логарифма не влияет на порядок роста (log_a n = (log_a b)·log_b n — константа-множитель). Константные множители и слагаемые младших порядков при n → ∞ игнорируются."}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Как сравнивать две функции на глаз и формально"}]},{"type":"orderedList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Метод пределов: рассмотрите L = lim n->∞ f(n)/g(n). Если L = 0, то f ∈ o(g). Если 0 < L < ∞, то f ∈ Θ(g). Если L = ∞, то f ∈ ω(g)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Правила прикидки: полиномиальные степени сравниваем по показателям; n^a << n^b, если a < b. Любой полином << экспоненты b^n. Логарифмы растут медленнее линейных функций: log n << n."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Иерархия типичных порядков роста (от медленного к быстрому)"}]},{"type":"table","content":[{"type":"tableRow","content":[{"type":"tableHeader","content":[{"type":"paragraph","content":[{"type":"text","text":"Порядок роста"}]}]},{"type":"tableHeader","content":[{"type":"paragraph","content":[{"type":"text","text":"Краткий комментарий/пример"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"1 (константная)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Доступ к элементу массива по индексу"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"log n"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Бинарный поиск"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"n"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Однопроходная обработка массива"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"n log n"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Сортировки сравнениями (merge/quick в среднем)"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"n^2"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Два вложенных цикла (пузырьковая сортировка)"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"n^3"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Три вложенных цикла (наивная матричная мультипликация)"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"2^n"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Полный перебор подмножеств/решений (экспонента)"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"n!"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Перебор всех перестановок (очень быстро растёт)"}]}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Примеры кода, иллюстрирующие разные скорости роста"}]},{"type":"codeBlock","attrs":{"language":"javascript"},"content":[{"type":"text","text":"// O(1): константное время — не зависит от n\nfunction getFirst(arr) {\n return arr[0];\n}\n\n// O(n): линейное время — один проход по массиву\nfunction sum(arr) {\n let s = 0;\n for (let i = 0; i < arr.length; i++) {\n s += arr[i];\n }\n return s;\n}\n\n// O(n log n): разделяй-и-властвуй (пример — сортировка слиянием)\nfunction mergeSort(arr) {\n if (arr.length <= 1) return arr;\n const mid = Math.floor(arr.length / 2);\n const left = mergeSort(arr.slice(0, mid));\n const right = mergeSort(arr.slice(mid));\n return merge(left, right);\n}\n\nfunction 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 return res.concat(a.slice(i)).concat(b.slice(j));\n}\n\n// O(n^2): два вложенных цикла — сравнение всех пар\nfunction hasDuplicateQuadratic(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}\n\n// Улучшение до O(n) с хеш-таблицей (меньшая скорость роста)\nfunction hasDuplicateLinear(arr) {\n const seen = new Set();\n for (const x of arr) {\n if (seen.has(x)) return true;\n seen.add(x);\n }\n return false;\n}"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Практические советы для собеседований"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Говорите в терминах входного размера n и используйте нотации O/Θ/Ω."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Игнорируйте константы и низшие члены: 3n^2 + 10n + 100 — это Θ(n^2)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Уточняйте лучший/средний/худший случаи и используемую модель данных (например, доступ к хеш-таблице амортизированно)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Различайте теорию и практику: при малых n алгоритм с большим порядком роста может быть быстрее из-за маленьких констант, но проиграет при росте n."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Типичные заблуждения и тонкости"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Big-O — это не точное время, а верхняя асимптотическая граница."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"n log n может быть больше n^2 при очень малых n, но асимптотически n log n растёт медленнее."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Представление входа важно: числа в двоичном виде меняют стоимость операций логарифмически."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Асимптотика по памяти — тоже скорость роста: например, структура данных с Θ(n) памяти."}]}]}]}]}

Что такое “скорость роста функции”?

Комментарии