对象数组访问时间是 O(1) 吗？

Question

我知道如果使用数学公式 array[n]=(start address of array + (n * size Of(type)) 从数组中访问某些内容需要 O(1) 时间，但假设您有一个 array of objects。这些对象可以有任意数量的字段，包括嵌套对象。我们可以认为访问时间是恒定的吗？

编辑-我主要是要求JAVA，但我想知道如果我选择另一种主流语言如python、c++、JavaScript是否有区别等等

例如下面的代码

class tryInt{
    int a;
    int b;
    String s;
    public tryInt(){
        a=1;
        b=0;
        s="Sdaas";
    }
}

class tryobject{
    public class tryObject1{
        int a;
        int b;
        int c;
    }
    public tryobject(){
        tryObject1 o=new tryObject1();
        sss="dsfsdf";
    }
    String sss;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello World!");
        Object[] arr=new Object[5];
        arr[0]=new tryInt();
        arr[1]=new tryobject();
        System.out.println(arr[0]);
        System.out.println(arr[1]);
    }
}

我想知道，既然tryInt类型的对象应该比tryobject类型的对象少space，数组现在怎么用公式array[n]=(start address of array + (n * size Of(type))，因为type不是更相同，因此这个公式 should/will 失败。

Answer 1

你的问题的答案是视情况而定。

如果可以在知道所需索引的情况下随机访问数组，是的，这是一个 O(1) 操作。

另一方面，如果数组中的每一项长度不同，或者数组存储为链表，则需要从数组的开头开始查找您的元素，跳过元素直到找到与您的索引对应的那个。这是一个 O(n) 操作。

在程序员和数据收集的现实世界中，这种 O(x) 的东西与数据的表示方式密不可分。

许多人保留 array 这个词来表示随机访问的 O(1) 集合。一本书的页面是一个数组。如果您知道页码，您可以翻到该页。（将书翻到正确的页面不一定是微不足道的操作。您可能必须先去图书馆找到正确的书。这个类比适用于多级计算机存储...硬盘驱动器/ RAM /多个级别处理器缓存）

人们将 list 用于顺序访问的 O(n) 集合。书页上的文本句子是一个列表。要找到第五句，您必须阅读前四句。

我在这里提到list和array这两个词的意思，对于专业程序员来说是一个重要的原因。我们的大部分工作是维护现有代码。在我们理所当然地急于完成事情的过程中，有时我们会抓住手头的第一个集合 class，有时我们会抓住错误的集合。例如，我们可能会获取一个 O(n) 的列表而不是一个 O(1) 的数组或一个 O(1，也许) 的散列。我们获取的集合非常适合我们的测试。但是，boom!，当应用程序成功并扩展到容纳大量数据时，性能就会下降。这种情况一直在发生。

要解决此类问题，我们需要对这些访问问题有实际的了解。我曾经继承了一个项目，它有一个自制的散列字典 class，在向字典中插入大量项目时消耗了 O(n cubed)。花了很多时间来研究时髦的集合-class 文档以弄清楚到底发生了什么。

Answer 2

答案取决于上下文。

在一些教科书中，将数组访问视为 O(1) 是很常见的，因为它简化了分析。公平地说，在当今的体系结构中，它是 O(1) cpu 指令。

但是：

随着数据集变大并趋于无穷大，内存已放不下。如果“数组”被实现为分布在多台机器上的数据库结构，那么您最终会得到一个树结构，并且可能具有对数的最坏情况访问时间。如果您不关心数据大小趋于无穷大，那么大 O 表示法可能不适合您的情况
在真实的硬件上，内存访问并不完全相同——有很多层缓存，缓存未命中会花费数百或数千个周期。内存访问的 O(1) 模型往往会忽略
在理论上工作，随机存取机器在 O(1) 中访问内存，但图灵机器不能。分层缓存效应往往被忽略。一些模型，如跨二分法 RAM 试图解释这一点。

简而言之，这是您的计算模型的属性。有许多有效且有趣的计算模型，选择什么取决于您的需要和情况。

Answer 3

一般。数组表示固定大小的内存范围，存储相同大小的元素。如果我们考虑这个通常的数组概念，那么如果对象是数组的成员，那么在引擎盖下你的数组存储对象引用并引用数组中的第 i 个元素你会找到 object/pointer 它的引用包含，复杂度为 O(1)，它指向的地址是语言要查找的内容。

但是，有些数组不符合这个定义。例如，在 Javascript 中，您可以轻松地将项目添加到数组中，这让我认为在 Javascript 中，数组与相同 size/type 的分配的固定大小范围的元素有些不同].此外，在 Javascript 中，您可以将任何类型的元素添加到数组中。所以，总的来说，我会说复杂度是 O(1)，但根据技术的不同，这条规则有很多重要的例外。

Answer 4

在 Java 中，Object 类型是对对象而不是对象本身的引用。也就是说，Object 类型的变量可以被认为是一个指针，表示“这里是你应该去哪里找到你的 Object”，而不是“我是一个真实的、诚实的 Object。”重要的是，无论 Object 变量指的是什么类型，这个引用的大小——用完的字节数——都是一样的。

因此，如果你有一个 Object[]，那么索引到该数组的成本确实是 O(1)，因为该数组中的条目都具有相同的大小（即，大小对象引用）。指向的对象的大小可能并不完全相同，如您的示例所示，但指针本身的大小始终相同，因此您给出的数学提供了一种在恒定时间内进行数组索引的方法。

对象数组访问时间是 O(1) 吗？

Is Array of Objects Access Time O(1)?

arrays

time-complexity