Почему произвольный доступ deque O (1) раз

Question

Я прочитал Доступ к STL по индексу по индексу равен O (1)? и . Как произвольный доступ к элементу в deque дает постоянную сложность по времени? , и он до сих пор не ' Мне кажется ясным, почему O (1) произвольный доступ гарантирован.

Я понимаю, что deque в STL реализован как массив указателей на смежные куски фиксированного размера. Таким образом, я понимаю, что цикл по фрагменту фиксированного размера равен O (1), потому что он не зависит от размера deque. Но чтобы определить, какой блок равен l oop, нам нужно l oop для массива указателей, что я не считаю операцией O (1), потому что массив указателей пропорционален размеру Deque?

Например, если у нас есть дека размером n и фиксированный размер чанка, скажем, m, наш массив указателей будет иметь размер потолка (н / м), то есть O (n) ? Я что-то неправильно понимаю?

Answer 1

Вы не зацикливаетесь на «массиве» указателей. Поиск указателя является операцией с постоянным временем, потому что вы можете найти блок, добавив константу к указателю к первому индексу в массиве указателей.

Например, используя вашу нотацию, если у вас есть n размер deque, с размером m, чтобы найти j -й элемент, вам нужно найти указатель на блок, содержащий j -й элемент, как вы сказали. Но это не подразумевает циклический переход по «массиву» указателей. В этом случае необходимо добавить константу j/m.