11. 多个参数¶

有时对算法进行恰当的分析需要多个参数来描述代价。 为说明这一概念，考虑一个计算图片中所有像素值出现次数排序的算法。 图片通常用二维数组表示，像素就是数组中的一个单元。 像素的值要么是颜色的编码值， 要么是图片在该像素处的强度值。 假设每个像素可以取 0 到 \(C - 1\) 范围内的任意整数值。 问题是要找出每种颜色值各有多少个像素， 然后按照每种颜色值在图片中出现的次数对这些颜色值排序。 假设图片是一个包含 \(P\) 个像素的矩形。 求解该问题的伪代码如下。

• Java
• C++

  for (i=0; i<C; i++) {   // Initialize count
     count[i] = 0;
  }
  for (i=0; i<P; i++) {   // Look at all of the pixels
     count[value(i)]++; // Increment a pixel value count
  }
  sort(count);          // Sort pixel value counts

  for (i=0; i<C; i++)   // Initialize count
     count[i] = 0;
  for (i=0; i<P; i++)   // Look at all of the pixels
     count[value(i)]++; // Increment a pixel value count
  sort(count, C);       // Sort pixel value counts

在这个例子中， count 是一个长度为 C 的数组， 存储每种颜色值的像素数。 函数 value(i) 返回像素 \(i\) 的颜色值。

第一个 for 循环（它初始化 count ）的时间 取决于颜色的数目 \(C\) 。 第二个循环（它确定每种颜色的像素数）的时间是 \(\Theta(P)\) 。 最后一行即对 sort 的调用，其时间取决于所用排序算法的代价。 我们假定排序算法在排序 \(P\) 个项时代价为 \(\Theta(P \log P)\) ， 因而算法总代价为 \(\Theta(P \log P)\) 。

这是该算法代价的一个好的表示吗？ 实际被排序的是什么？ 不是像素，而是颜色。 如果 \(C\) 远小于 \(P\) 呢？ 那么 \(\Theta(P \log P)\) 的估计就偏悲观， 因为被排序的项远少于 \(P\) 个。 相反，对于查看每个像素的步骤， 我们应当用 \(P\) 作为分析变量； 对于查看颜色的步骤，用 \(C\) 作为分析变量。 于是，初始化循环得到 \(\Theta(C)\) ， 像素计数循环得到 \(\Theta(P)\) ， 排序操作得到 \(\Theta(C \log C)\) 。 这得到总代价 \(\Theta(P + C \log C)\) 。

为什么我们不能简单地用 \(C\) 的值作为输入规模， 并说算法的代价是 \(\Theta(C \log C)\) ？ 因为 \(C\) 通常远小于 \(P\) 。 例如，一幅图片可能有 1000 \(\times\) 1000 个像素， 颜色范围为 256 种。 于是 \(P\) 是一百万，远大于 \(C \log C\) 。 但是，如果 \(P\) 较小，或 \(C\) 较大 （即使它仍小于 \(P\) ）， 那么 \(C \log C\) 就可能成为较大的量。 因此，两个变量都不应被忽略。