10

在堆栈溢出答案之一中，为什么 ArrayList.get 是 O(1) 而不是 O(n)

响应者说 ArrayList 由一个数组和一个

      RangeCheck(index);

是什么决定了恒定的时间复杂度而不是线性的！我正试图解决这个问题，任何数组都不必至少部分搜索数组中可能 n 个字段的百分比，从而以某种方式构成 O(n) 搜索（如果要寻找的元素在数组的 n-1 位置 - 这不会是 O(n) 搜索吗？它仍然是我认为是 O(n) 复杂度的一级 for 循环？

4

3 回答 3

19

数组按顺序放置在内存中。这意味着，如果它是一个整数数组，每个整数使用 4 个字节，并且从内存地址 1000 开始，则下一个元素将在 1004 处，下一个元素将在 1008 处，依此类推。因此，如果我想要数组中位置 20 的元素，get()则必须计算以下代码：

1000 + 20 * 4 = 1080

获得元素的确切内存地址。好吧，RAM 存储器之所以被称为随机存取存储器，是因为它们的构建方式使得它们具有硬件多路复用器的层次结构，允许它们在给定地址的情况下以恒定的时间访问任何存储的内存单元（字节？）。

因此，两个简单的算术运算和一个对 RAM 的访问被称为 O(1)。

于 2013-09-25T17:56:58.300 回答
14

按照建议发布为答案：

ArrayList.get(int) 不搜索。它直接返回由提供的索引寻址的元素...与数组完全一样-因此得名。

ArrayList.get(int) 来源：

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

其中 rangeCheck(int) 是：

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

elementData() 是：

E elementData(int index) {
    return (E) elementData[index];
}

然而，链接列表将有一个O(n)获取：它必须进入下一个元素，直到达到所需的索引......

public E get(int index) {
    return entry(index).element;
}

entry(int)在哪里（这就是使它成为 O(n) 的原因）：

private Entry<E> More ...entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    Entry<E> e = header;

    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

（注意：它是双链表，因此通过选择最接近所需结果的端点来节省一些时间，但这仍然是 O(n) ）

于 2013-09-25T17:53:11.633 回答
0

访问数组中的特定索引是一个常数时间操作，因为它涉及从数组对象中获取基内存地址，并访问基地址 + 索引乘以元素类型大小的内存。由于中间的所有元素都被跳过，因此访问时间受一个常数的限制。

该ArrayList.get(int)方法是对直接数组访问的精简包装，因此它也受一个常量的限制。

于 2013-09-25T17:53:20.557 回答