{"type":"doc","content":[{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"Короткий ответ"}]},{"type":"paragraph","content":[{"type":"text","text":"O-большое (Big O) — это математическая нотация для описания верхней асимптотической границы роста времени выполнения или потребления памяти алгоритма в зависимости от размера входа n. Она абстрагируется от констант и менее значимых слагаемых и показывает, как алгоритм масштабируется при росте n."}]},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"Подробное объяснение"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Что такое Big O и зачем оно нужно"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Big O оценивает, насколько быстро растёт время (или память) алгоритма при увеличении размера входных данных n."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Используется для сравнения алгоритмов независимо от железа, языка и конкретных реализаций."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Это верхняя граница: худший (или максимум вплоть до константы) рост функции затрат при больших n."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Формальное определение и сравнение с другими нотациями"}]},{"type":"paragraph","content":[{"type":"text","text":"Формально: f(n) = O(g(n)), если существуют положительные константы c и n0 такие, что для всех n ≥ n0 выполнено f(n) ≤ c · g(n)."}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Big Ω (омега) — нижняя граница: f(n) ≥ c · g(n) для достаточно больших n."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Big Θ (тэта) — точная асимптотика (и верхняя, и нижняя границы совпадают по порядку)."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Что обычно измеряют"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Временная сложность: количество элементарных операций/шагов в зависимости от n."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Пространственная (память): дополнительная память, которую алгоритм использует сверх входных данных."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Правила чтения и оценки Big O"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Игнорируем константы: O(2n) → O(n), O(n + 5) → O(n)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Оставляем доминирующий член: O(n^2 + n) → O(n^2)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Последовательные фрагменты складываются: O(a) + O(b) → O(a + b) → доминирующий порядок."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Вложенные циклы перемножаются: внешний O(n), внутренний O(m) → O(n·m). Для n=m → O(n^2)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Деление задачи пополам ведёт к логарифму: бинарный поиск → O(log n)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Рекурсии вида T(n)=2T(n/2)+O(n) → O(n log n); T(n)=T(n−1)+O(1) → O(n); T(n)=T(n−1)+O(n) → O(n^2)."}]}]}]},{"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":"O(1)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Доступ к элементу массива по индексу, push/pop в стек"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"O(log n)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Бинарный поиск, балансированные деревья (поиск/вставка/удаление)"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Линейный проход: поиск max, сумма массива"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n log n)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Сортировки сравнениями (merge sort, quicksort в среднем), построение кучи"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n^2)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Два вложенных цикла по одному массиву, простые сортировки (bubble/selection/insertion)"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"O(2^n)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Перебор подмножеств, наивный рекурсивный Fibonacci"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n!)"}]}]},{"type":"tableCell","content":[{"type":"paragraph","content":[{"type":"text","text":"Перебор всех перестановок (задачи комбинаторной оптимизации)"}]}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Примеры кода с оценкой сложности"}]},{"type":"codeBlock","content":[{"type":"text","text":"// O(1): доступ по индексу\nfunction getFirst(arr) {\n return arr[0];\n}\n\n// O(n): сумма элементов\nfunction sum(arr) {\n let s = 0;\n for (const x of arr) s += x;\n return s;\n}\n\n// O(log n): бинарный поиск (массив отсортирован)\nfunction binarySearch(arr, target) {\n let l = 0, r = arr.length - 1;\n while (l <= r) {\n const m = (l + r) >> 1;\n if (arr[m] === target) return m;\n if (arr[m] < target) l = m + 1; else r = m - 1;\n }\n return -1;\n}\n\n// O(n log n): merge sort\nfunction mergeSort(a) {\n if (a.length <= 1) return a;\n const mid = a.length >> 1;\n const left = mergeSort(a.slice(0, mid));\n const right = mergeSort(a.slice(mid));\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 return res.concat(left.slice(i), right.slice(j));\n}\n\n// O(n^2): проверка дубликатов вложенными циклами\nfunction hasDuplicatesQuadratic(a) {\n for (let i = 0; i < a.length; i++) {\n for (let j = i + 1; j < a.length; j++) {\n if (a[i] === a[j]) return true;\n }\n }\n return false;\n}\n\n// O(2^n): генерация всех подмножеств\nfunction subsets(a) {\n const res = [];\n const n = a.length;\n for (let mask = 0; mask < (1 << n); mask++) {\n const cur = [];\n for (let i = 0; i < n; i++) {\n if (mask & (1 << i)) cur.push(a[i]);\n }\n res.push(cur);\n }\n return res;\n}\n\n// O(n!): все перестановки\nfunction permutations(a) {\n const res = [];\n function backtrack(i) {\n if (i === a.length) { res.push(a.slice()); return; }\n for (let j = i; j < a.length; j++) {\n [a[i], a[j]] = [a[j], a[i]];\n backtrack(i + 1);\n [a[i], a[j]] = [a[j], a[i]];\n }\n }\n backtrack(0);\n return res;\n}"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Почему эти оценки такие"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Доступ по индексу — O(1), так как адрес вычисляется константно и элемент читается за фиксированное время (в модели RAM)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Линейный проход — O(n): одна операция на элемент, всего пропорционально числу элементов."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Бинарный поиск — O(log n): на каждом шаге диапазон делится пополам, число шагов пропорционально количеству делений до 1."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Merge sort — O(n log n): глубина рекурсии log n, на каждом уровне слияние обходится в O(n)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Два вложенных цикла — O(n^2): число пар (i, j) растёт как квадрат n."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Подмножества — O(2^n): каждое из n элементов либо берётся, либо нет — всего 2^n комбинаций."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Перестановки — O(n!): число перестановок длины n равно n!."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Сложность по памяти (пространственная)"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Дополнительный массив на n элементов — O(n) памяти."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Глубина рекурсии: merge sort использует O(n) вспомогательной памяти для слияния и O(log n) стека вызовов (если считать только стек)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Хэш-таблица для уникализации — O(k), где k — число уникальных элементов, обычно O(n)."}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Частые ошибки при использовании Big O"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Путать средний, лучший и худший случаи: Big O — про верхнюю границу; средний случай иногда отличается (например, quicksort)."}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Игнорировать скрытые константы: O(n) с очень большим коэффициентом может быть медленнее O(n log n) на реальных 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":"Назовите временную и пространственную сложность, укажите, это худший, средний или лучший случай."}]}]}]}]}

Что означает символ O (Big O)??

Комментарии