0

我想计算以下用于调整二进制图像大小的算法的大 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)。然而，双线性插值肯定比最近的邻居慢得多。您能否解释一下如何正确计算复杂度？

4

1 回答 1

0

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

这绝不意味着这两个程序的执行速度一样快。它仅仅意味着如果你增加new_height和/或new_width到无穷大，两个程序之间的执行时间比率既不会变为无穷大，也不会为零。

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

于 2022-01-23T19:47:23.963 回答