含N个MyClass元素的ArrayList调用Collections.reverse()的时间复杂度

嘿，这个问题问得很到位！咱们直接说结论：当你对一个包含N个MyClass元素的ArrayList调用Collections.reverse()时，时间复杂度是O(N)。

为什么是线性时间呢？咱们来扒一扒背后的逻辑：

• ArrayList本质是基于数组实现的，支持O(1)的随机访问。Collections.reverse()实际上会调用ArrayList自身的reverse()方法（JDK源码里就是这么实现的）。
• 这个方法的核心逻辑很简单：用双指针，一个从列表头部（索引0）开始，一个从尾部（索引size-1）开始，交换两个指针指向的元素，然后头部指针右移、尾部指针左移，直到两个指针相遇或者交叉。
• 总共需要交换的次数是N/2次，不管N是奇数还是偶数，这个次数都是和N成正比的线性量级。而每次交换操作都是数组元素的直接赋值，属于O(1)的常数时间操作。

给你看一段简化版的JDK源码，更直观：

public void reverse() {
    modCount++;
    int hi = size - 1;
    for (int lo = 0; lo < hi; lo++, hi--) {
        E temp = elementData[lo];
        elementData[lo] = elementData[hi];
        elementData[hi] = temp;
    }
}

这里循环的次数正好是floor(N/2)，所以整体的时间复杂度就是O(N)——毕竟线性时间的定义就是操作数和输入规模成线性比例嘛。

内容的提问来源于stack exchange，提问作者Prestyy