История изменений
Исправление aist1, (текущая версия) :
Если мне не изменяет память, то для массива самое лучшее, что можно получить для insert() это O(sqrt(N)), если хочется O(1) для access(). Пруфов не найду. Видел когда-то давно в каком-то пейпере.
Еще надо учитывать, что все эти оценки в данном случае уже носят чисто теоретический интерес, так как там, скорее всего, будут плохие скрытые константы.
Исходная версия aist1, :
Если мне не изменяет память, то для массива самое лучшее, что можно получить для insert() это O(sqrt(N)), если хочется O(1) для access(). Пруфов не найду. Видел когда-то давно в каком-то пейпере.