algorithm - 普通算法的平均情况复杂度

Question

P(x,y,z){
    print x
    if(y!=x) print y
    if(z!=x && z!=y) print z
}

此处的简单算法，值 x、y、z 是从 {1,...r} 中随机选择的 与 r >= 1。我试图确定此算法的平均案例复杂度，并根据打印语句的数量来衡量复杂度。

这里最好的情况是 T(n) = 1 或 O(1)，当 x=y=z 且概率为 1/3 时。
当 x!=y!=z 且概率为 2/3 时，这里最坏的情况仍然是 T(n) = 3 或 O(1)。

但是当涉及到数学推导平均情况时:
样本空间是 n 个可能的输入，样本空间的概率是 1/n 机会那么，如何计算平均案例复杂度？ (这是我画空白的地方..)

Answer 1

你的算法有三种情况:

1. 所有三个数字都相等。这个概率是 1/r，因为一旦您选择了x，y 和z 就只有一个选择。成本对于这种情况是 1。
2. x != y，但 x == z 或 y == z。这个概率是 1/r * (1/(r - 1))* 1/2,因为一旦你选择了 x，y 就只有 r -1 个选择，而 z 只能是这两个选择之一。成本 = 2。
3. 所有三个数字都不相同。三者都不同的概率是1/r * (1/(r - 1))*(1/(r - 2))。成本 = 3。

因此，平均情况可以计算为:

1/r  + 1/r * (1/(r - 1)) + 1/r * (1/(r - 1))*(1/(r - 2)) * 3 == O(1)

编辑:上面的表达式是 O(1)，因为整个表达式由常量组成。