假设我得到了一个行主数组。
int* a = (int *)malloc( 9 x 9 x sizeof(int));
将此视为 2D 9x9 数组,其中(行,列)索引对应于 [行 * 9 + 列] 有没有一种方法可以在亚线性时间内从这个数组中选择一个列? 由于列不会连续,我们不能像获取单行那样直接执行 memcpy。
我猜线性时间的解决方案很明显,但我希望有一些次线性的解决方案。
谢谢。
最佳答案
次线性 是什么意思不清楚。如果您将二维数组视为 NxN 大小,则 N 上的次线性不可能。要复制 N 个元素,您需要执行 N 个复制操作,复制将与被复制的元素数量成线性。
关于memcpy
的评论似乎表明您错误地认为memcpy
在被复制的元素数量上是次线性。它不是。 memcpy
的优点是隐藏在big-O符号中的常量很小,但操作与被复制的内存大小成线性关系。
下一个问题是大 O 分析是否真的有意义。如果您的数组是 9x9,那么隐藏在大 O 符号常量中的效果可能比复杂性更重要。
关于c++ - 如何在次线性时间内从行优先数组中选择列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9537304/