4.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\) 就可能成为较大的量。因此，两个变量都不应被忽略。