二维数组的 Big-O 插入

Question

如果我有 N x N 二维数组，名称是 a.

int a[N][N];

当我在任何数组中插入任何值时，例如 a[N-1][N-1]=1，需要多少时间？

O(N^2) 或 O(1)?

Answer 1

你不会插入吧？你正在分配，直接到一个特定的地址，你不需要事先找出正确的位置。

也就是说你不需要做任何循环，不需要经过任何计算就可以找到位置并赋值，而且内存已经分配好了。

所以它是 O(1)，常数与输入无关。

Answer 2

由于您直接将值分配给数组中的特定位置，因此 ORDER 将为 O(1)

如果您通过 2 个循环对其进行迭代，那么它将是 O(n^2) 因为对于每个 i 都会有一个完整的 j 迭代。例如：

for(int i=0; i<n;i++){
 for(int j=0; j<n;j++){
 }
}

Answer 3

我猜你说的是有序数组，因为对于无序数组来说它是 O(1)。您将元素 [n][m] 复制到末尾并将新元素放入 [n][m]
我认为你是在谈论插入，而不是赋值，因为赋值是 O(1)。
如果你的数组是有序的，那么 O(N*N) 移动所有元素

Answer 4

c 中的赋值操作可能被威胁为原语的 O(1)

但是：如果您正在为随机位置做很多分配，其他玩家就会出现...

考虑以下 2 个示例：

ex1.c:

#define W 1<<12
#define H W
int a[H][W];

int main(){

    for(int j=0;j< W ;j++){
    for(int i=0;i< H ;i++){
       a[i][j]=1;
    }
    }
    return 0;
}

ex2.cpp:

#define W 1<<12
#define H W
int     a[H][W];

int main(){

    for(int j=0;j< H ;j++){
    for(int i=0;i< W ;i++){
       a[i][j]=1;
    }
    }
        return 0;
}

CFLAGS=-O3 g++ ex1.c -o e1  && g++ ex2.c -o e2  && time ./e1 && time ./e2 && time ./e1
user    0m0.332s
user    0m0.048s
user    0m0.320s

如您所见，ex1 速度较慢！

取决于所使用的编译器优化级别及其能力，这两者的行为可能非常不同，即使它们在做同样的事情

如果您正在进行一些随机访问，cpu L1 缓存将开始丢失页面，这将导致 pull/put 页面浪费一些周期。如果 L2 能够为 L1 的失误提供服务，那没关系 - 如果 L2 有失误，同样的情况也会发生在 L2 级别......我想你明白了 ;)

更多： http://en.wikipedia.org/wiki/CPU_cache

你甚至可能会造成数据危害，它的影响要小得多——但非常有趣 http://en.wikipedia.org/wiki/Hazard_%28computer_architecture%29#Data_hazards

二维数组的 Big-O 插入

Big-O insert for 2 dimensional array

c

c++

arrays

big-o