如何使用常数值填充2D数组,效率高于n ^ 2？

Question

这是一个普遍的问题,它可以适用于任何给定的语言,如C,C++,Java等.
我认为你实现它的任何方式,你不能比使用2个循环更有效,这提供了n ^ 2的效率.

for(i=0;i<n;i++)
 for(j=0;j<n;j++)
  a[i][j]=1;

我最近在接受采访时被问到这个问题,并且想不出更有效的方法.我从访调员那里得到的是,我可以使用递归或将2D数组转换为链表,使其比n ^ 2更有效.任何人都知道这是否可能,如果有,怎么样？至少在理论上,如果不是实际的话.

编辑:实际的问题给了我两个单元格的坐标,我必须用1填充所有可能的最短路径所采用的路径.例如,如果我有一个5x5矩阵,我的两个坐标是(2,0)和( 3,3),我必须填写:
(2,0)(2,1)(2,2)(2,3)(3,0)(3,1)(3,2)(3, 3)
同时留下其余的细胞.

Answer 1

这取决于你的意思.如果问题是关于普通数组,意味着一系列连续存储器位置和初始化你的意思是在这个"矩阵"的每个存储器位置放一个值,那么答案是否定的,优于O(n*m)是不可能的,我们可以证明:

让我们假设算法fill(A[n][m], init_val)是正确的(即填充所有内存位置A)具有g(n,m)小于O(n*m)(意思g(n,m)不是其中一部分?(n*m))的复杂度,那么对于足够大n而m我们将具有g(n,m) < n*m=内存位置的数量.由于填充存储器位置需要一个操作,算法fill可以填充大多数g(n,m)位置[实际上是一半因为它还必须至少执行"选择"不同存储器位置的操作,除非硬件提供组合操作]严格小于n*m,这暗示算法fill不正确.

如果填充k内存位置需要恒定时间,则同样适用,您只需选择更大的值n和m值.

正如其他已经建议的那样,您可以使用其他数据结构来避免O(n^2)初始化时间.amit suggestion使用某种延迟评估,它允许你根本不初始化数组,但只在访问元素时才这样做.

请注意,这会?(n^2)在开始时消除成本,但需要更复杂的操作来访问阵列的元素,并且还需要更多内存.

目前尚不清楚你的采访者的意思:将数组转换为链表需要?(L)时间(其中L是数组的长度),因此简单地将整个矩阵转换为链表需要?(n^2)时间加上真正的初始化.使用递归根本没有帮助,你只是最终T(n) = 2T(n/2) + O(1)会再次出现,这会再次导致渐近复杂性没有任何好处.

作为一般规则,所有算法必须扫描至少所有输入,除了它们事先具有某种形式的知识(例如,元素被排序).在您的情况下,扫描的空间是?(n^2),因此每个想要填充它的算法必须至少?(n^2).任何低于这种复杂度的东西要么做出一些假设(例如,内存默认包含初始值 - > O(1)),或者解决不同的问题(例如使用惰性数组或其他数据结构).