我看过 STL deque通过索引访问是O(1)? 而 在deque中，一个元素的随机访问如何给出恒定的时间复杂度？ 而且我还是不明白为什么要保证O(1)的随机访问。
我理解STL中的deque是以一个指向连续的 固定的 大小的块。所以我理解在一个固定大小的chunk上循环是O(1)，因为它与deque的大小无关。但要找到要循环的chunk，我们需要循环一个指针数组，我不相信这是一个O(1)操作，因为指针数组与deque的大小成正比。
例如，如果我们有一个 n 大小的deque和固定的块大小是说。m，我们的指针数组的大小为 ceiling(nm)，也就是 O(n)？我是不是理解错了什么？
你并没有在指针的 "数组 "上循环。寻找指针是一个恒时操作，因为你可以通过向指针数组中的第一个索引添加一个常量来找到块。
例如，使用你的符号，如果你有一个 n-大小 deque，与 m-大小的块状物，以找到 j-元素，你需要找到指向包含了 j第-个元素，如你所说。但这并不涉及到循环处理指针的 "数组"。在这种情况下，需要添加的常量是 j/m.