algorithm - 如何用常数值填充二维数组，效率比 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;

我最近在一次面试中被问到这个问题，想不出更有效的方法。我从面试官那里得到的只是，我可以使用递归或将二维数组转换为链表，使其比 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) locations[实际上是一半，因为它还必须至少执行一个操作来“选择”不同的内存位置，除非硬件提供组合操作]严格小于n*m ，这意味着算法 fill不正确。

填写k同理内存位置需要常数时间，你只需选择更大的 n和 m值(value)观。

正如其他人已经建议的那样，您可以使用其他数据结构来避免 O(n^2)初始化时间。 amit 建议使用某种惰性求值，它允许您根本不初始化数组，而仅在访问元素时才进行初始化。

请注意，这会删除 Ω(n^2)开始时成本较高，但需要更复杂的操作来访问数组的元素，并且还需要更多内存。

不清楚面试官的意思:将数组转换为链表需要 Ω(L)时间(其中 L 是数组的长度)，因此简单地将整个矩阵转换为链表需要 Ω(n^2)时间加上真正的初始化。使用递归根本没有帮助，您只会以 T(n) = 2T(n/2) + O(1) 之类的重复出现而告终这将再次导致对渐近复杂性没有任何好处。

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