c++ - 如何在次线性时间内从行优先数组中选择列？

Question

假设我得到了一个行主数组。

int* a = (int *)malloc( 9 x 9 x sizeof(int));

将此视为 2D 9x9 数组，其中(行，列)索引对应于 [行 * 9 + 列]有没有一种方法可以在亚线性时间内从这个数组中选择一个列？由于列不会连续，我们不能像获取单行那样直接执行 memcpy。

我猜线性时间的解决方案很明显，但我希望有一些次线性的解决方案。

谢谢。

Answer 1

次线性 是什么意思不清楚。如果您将二维数组视为 NxN 大小，则 N 上的次线性不可能。要复制 N 个元素，您需要执行 N 个复制操作，复制将与被复制的元素数量成线性。

关于memcpy 的评论似乎表明您错误地认为memcpy 在被复制的元素数量上是次线性。它不是。 memcpy的优点是隐藏在big-O符号中的常量很小，但操作与被复制的内存大小成线性关系。

下一个问题是大 O 分析是否真的有意义。如果您的数组是 9x9，那么隐藏在大 O 符号常量中的效果可能比复杂性更重要。