Введение

Привет, хабр. Я хотел бы рассказать о забавной структуре данных под названием «Массив без инициализации».

Во многих языках программирования для корректной работы с массивом необходимо его инициализировать сразу после объявления. Будем считать, что инициализация есть присвоение всем элементам какого-либо одинакового значения. Если массив состоит из N элементов, алгоритмическая сложность этой операции — O(N). Однако, можно показать, что располагая в трое большим объемом памяти, можно обойтись инициализацией за O(1).