如何使用 O(n) 内存在 O(n) 时间内构造多维数组
How to construct multidimensional array in O(n) time using O(n) memory
我正在实现一个名为 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];
}
您的执行时间为 O(n)
,n
为 height * width
。想想看。如果将宽度加倍,则执行时间也会加倍。如果将高度加倍,执行时间也会加倍。这就是 O(n)
的意思。
您的内存占用量是 width * height * size_of_int + (height + 1) * array_overhead
(一个外部数组加上每行一个数组)。除了数组的微小开销外,如果将宽度加倍,则内存也会加倍。如果将高度加倍,则内存加倍。所以,O(n)
内存。
我正在实现一个名为 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];
}
您的执行时间为 O(n)
,n
为 height * width
。想想看。如果将宽度加倍,则执行时间也会加倍。如果将高度加倍,执行时间也会加倍。这就是 O(n)
的意思。
您的内存占用量是 width * height * size_of_int + (height + 1) * array_overhead
(一个外部数组加上每行一个数组)。除了数组的微小开销外,如果将宽度加倍,则内存也会加倍。如果将高度加倍,则内存加倍。所以,O(n)
内存。