如何使用O(n)内存在O(n)时间内构造多维数组

Question

我正在实现一个叫做IntegralImage的类，它有一个2D数组作为实例变量。2D数组表示一个图像，高度是第一个索引，宽度是第二个索引。以下代码是否在O(n)时间内构建2D数组，其中n是像素数(高度*宽度)?我也不明白到底什么是内存使用和如何确定它。我必须使用O(n)内存来构建数组。

private final int[][] integralImage;
private final int imageHeight; // height of image (first index)
private final int imageWidth; // width of image (second index)
public IntegralImage(int[][] image) {
    imageHeight = image.length;
    imageWidth = image[imageHeight - 1].length;
    integralImage = new int[imageHeight][imageWidth];
    int row,column;
    for(row = 0 ; row < imageHeight ; row++)
        for(column = 0 ; column < imageWidth; column++)
            integralImage[row][column] = image[row][column];
}

Answer 1

执行时间为O(n)，其中n为height * width。想想看。如果宽度增加一倍，执行时间也会增加一倍。如果高度翻倍，执行时间也会翻倍。这就是O(n)的意思。

您的内存占用是width * height * size_of_int + (height + 1) * array_overhead(一个外部数组加上每行一个数组)。除了数组的开销很小之外，如果宽度加倍，内存也会加倍。如果高度翻倍，内存也会翻倍。O(n)内存