algorithm - 我如何计算该元素唯一性问题解决方案的平均成本？

Question

在书中Introduction to the Design & Analysis of Algorithms ，针对元素唯一性问题提出如下解决方案:

ALGORITHM UniqueElements(A[0 .. n-1])
// Determines whether all the elements in a given array are distinct
// Input: An array A[0 .. n-1]
// Output: Returns "true" if all the elements in A are distinct
//         and false otherwise.
for i := 0 to n - 2 do
   for j := i + 1 to n - 1 do
      if A[i] = A[j] return false
return true

如何计算此算法的平均成本(即给定 n 的比较次数)？关于输入的合理假设是什么？

Answer 1

如果您对输入一无所知，那么合理的假设是它是随机的。如果是这样，并且如果可能的选择空间很大(例如所有实数的集合)，那么两个元素相同的可能性很小。 (在数学上，我们说两个随机选择的实数不同的事件是 almost sure 。)

这意味着您的平均情况等于最坏情况:您必须扫描数组中的每个元素以确保每个元素都是不同的。那么比较的次数就是n * (n - 1)/2，也就是1 ... n的总和。