如何获得 bilinear/nearest 邻域插值算法的复杂度？ （计算大O）

Question

我想计算以下用于调整二值图像大小的算法的大 O：

双线性插值:

double scale_x = (double)new_height/(height-1);
        double scale_y = (double)new_width/(width-1);

        for (int i = 0; i < new_height; i++)
        {
            int ii = i / scale_x;
            for (int j = 0; j < new_width; j++)
            {
                int jj = j / scale_y;
                double v00 = matrix[ii][jj], v01 = matrix[ii][jj + 1],
                        v10 = matrix[ii + 1][jj], v11 = matrix[ii + 1][jj + 1];
                double fi = i / scale_x - ii, fj = j / scale_y - jj;
                double temp = (1 - fi) * ((1 - fj) * v00 + fj * v01) +
                    fi * ((1 - fj) * v10 +  fj * v11);
                if (temp >= 0.5)
                    result[i][j] = 1;
                else
                    result[i][j] = 0;
            }
        }

最近邻插值

double scale_x = (double)height/new_height;
    double scale_y = (double)width/new_width;

    for (int i = 0; i < new_height; i++)
    {
        int srcx = floor(i * scale_x);
        for (int j = 0; j < new_width; j++)
        {
            int srcy = floor(j * scale_y);
            result[i][j] = matrix[srcx][srcy];
        }
    }

我假设它们的复杂度都是循环维度，即 O(new_height*new_width)。然而，双线性插值肯定比最近的邻居慢得多。您能否解释一下如何正确计算复杂性？

Answer 1

它们都是 运行 Theta(new_height*new_width) 时间，因为除了循环迭代之外，所有操作都是常数时间。

这绝不意味着这两个程序的执行速度相同。这只是意味着如果你将new_height and/or new_width增加到无穷大，两个程序之间的执行时间比率既不会变成无穷大也不会变成零。

（这是假设整数类型是无界的，并且所有算术运算都是独立于操作数长度的常数时间运算。否则将有另一个相关因素计算算术成本。）