{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Короткий ответ" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Доступ по индексу в обычном массиве и динамическом массиве (Array, std::vector, ArrayList, Python list, JS Array) — O(1). В связных списках — O(n). В деревьях/rope/персистентных векторах — O(log n) (часто O(logₖ n))." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Подробное объяснение" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Под «доступом по индексу» понимают операцию получить элемент по позиции i. Сложность зависит от внутреннего устройства структуры данных." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Почему массивы дают O(1)" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Непрерывная память: элемент i лежит по адресу base + i * size, вычисляется за константное время." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Сложность не зависит от n (количества элементов), только от i и размера элемента." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Проверка границ, кэш-попадания, page fault — это константные факторы, они не меняют асимптотику." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Примеры кода" }] }, { "type": "codeBlock", "attrs": { "language": "cpp" }, "content": [ { "type": "text", "text": "// C++: статический массив и std::vector — индексирование O(1)\n#include \n#include \nint main(){\n int a[5] = {10,20,30,40,50};\n std::vector v = {10,20,30,40,50};\n std::cout << a[3] << \" \" << v[3] << \"\\n\"; // 4-й элемент, O(1)\n}" } ] }, { "type": "codeBlock", "attrs": { "language": "python" }, "content": [ { "type": "text", "text": "# Python: list — динамический массив, доступ по индексу O(1)\narr = [10, 20, 30, 40, 50]\nprint(arr[3]) # 40" } ] }, { "type": "codeBlock", "attrs": { "language": "javascript" }, "content": [ { "type": "text", "text": "// JavaScript: Array — средний случай O(1) для плотных массивов\nconst arr = [10, 20, 30, 40, 50];\nconsole.log(arr[3]); // 40" } ] }, { "type": "codeBlock", "attrs": { "language": "java" }, "content": [ { "type": "text", "text": "// Java: Array и ArrayList — доступ по индексу O(1)\nimport java.util.*;\nclass Main{\n public static void main(String[] args){\n int[] a = {10,20,30,40,50};\n System.out.println(a[3]); // 40\n List list = new ArrayList<>(Arrays.asList(10,20,30,40,50));\n System.out.println(list.get(3)); // 40\n }\n}" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Когда доступ по индексу не O(1)" }] }, { "type": "table", "content": [ { "type": "tableRow", "content": [ { "type": "tableHeader", "content": [{ "type": "text", "text": "Структура" }] }, { "type": "tableHeader", "content": [{ "type": "text", "text": "Сложность" }] }, { "type": "tableHeader", "content": [{ "type": "text", "text": "Комментарий" }] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [{ "type": "text", "text": "Односвязный/двусвязный список" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "O(n)" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "Нужно пройти i узлов от головы/хвоста." }] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [{ "type": "text", "text": "Деревья (B-дерево, сегментное, Fenwick по индексу)" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "O(log n)" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "Переход по уровням дерева." }] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [{ "type": "text", "text": "Rope/верёвочная строка" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "O(log n)" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "Строка — дерево кусков; поиск по индексу идёт по дереву." }] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [{ "type": "text", "text": "Персистентный вектор (напр. Clojure)" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "O(logₖ n), обычно O(log₃₂ n)" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "Дерево с высокой ветвистостью даёт почти константную глубину." }] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [{ "type": "text", "text": "Deque/LinkedList (Java) по индексу" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "O(n)" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "Нет прямого случайного доступа." }] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [{ "type": "text", "text": "JS разрежённые массивы" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "Амортизированно O(1), высокая константа" }] }, { "type": "tableCell", "content": [{ "type": "text", "text": "Могут храниться как хеш-таблица/элементы проперти, без плотного буфера." }] } ] } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Строки: доступ к i-му байту/код-юниту — обычно O(1). Но доступ к i-му графемному кластеру (видимому «символу» Unicode) может требовать прохода — вплоть до O(n)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Ассоциативные массивы/словари не индексируются по позиции — там доступ по ключу, обычно амортизированно O(1), а не по индексу." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Амортизированность vs худший случай" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Динамические массивы иногда перевыделяют память при росте; это влияет на операции вставки/расширения, но не на чтение по индексу: get(i) остаётся O(1) в худшем случае. Вставки/удаления в середину — O(n), но это другая операция." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Итог" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Если структура — непрерывный массив (в т.ч. динамический), доступ по индексу — O(1). Как только данные разбиваются на узлы или уровни (списки, деревья, rope, персистентные структуры), сложность увеличивается до O(n) или O(log n)." } ] } ] }

Какова временная сложность доступа по индексу?

Комментарии