根据this documentation ，rotate方法collections.deque具有线性时间复杂度。也就是说，对于 collections.deque对象d , d.rotate(k) ，需要 O(k) 时间。为什么会这样？
collections.deque是双向链表的实现。难道仅仅通过更改恒定数量的引用就可以将双端队列的前 k 个元素移动到双端队列的末尾吗(假设 k 不大于双端队列中元素的总数 n)？如果可能的话，d.rotate(k)可以在常数时间内完成，O(1)，那为什么不 d.rotate(k)在 O(1) 内完成？
附注假设k <= n是合理的，因为这是最常见用法的情况。
最佳答案
在双向链表中查找位置 k 处的元素需要 O(k) 时间。
重新排列指针可能是常数时间，但你必须首先找到它们应该指向的位置。
关于python - 为什么collections.deque的rotate()方法具有线性时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63878383/