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

Question

我正在实现一个名为 IntegralImage 的 class，它有一个二维数组作为实例变量。二维数组表示图像，高度是第一个索引，宽度是第二个索引。以下代码是否在 O(n) 时间内构造二维数组，其中 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)内存。