0 
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。当概率为 2/3 时，
这里最坏的情况仍然是 T(n) = 3 或仍然是 O(1) 。x!=y!=z

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

4

4 回答 4

1

您的算法有三种情况：

  1. 所有三个数字都相等。这个概率是1/r，因为一旦你选择了x ，对于y和对于z只有一个选择。本案例的费用为 1。
  2. x != y，但x == z或y == z。这个概率是 1/r * (1/(r - 1))* 1/2，因为一旦你选择了 x，你就只剩下 r -1 个选择给 y，而 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)，因为整个表达式是由常量组成的。

于 2012-05-21T12:48:18.710 回答
0

平均情况将介于最好和最坏情况之间；对于这个特殊问题，这就是您所需要的（至少就 big-O 而言）。

于 2012-05-20T23:36:27.803 回答
0

1）您至少可以对一般情况进行编程吗？编写（伪）代码并对其进行分析，这可能很明显。您实际上可能对其进行了次优编程，并且可能存在更好的解决方案。这是非常典型的，它是计算机科学数学领域解谜的一部分，例如，如果你只是想编写一个排序代码，你很难自己发现快速排序。

2）如果可以，然后运行蒙特卡罗模拟并绘制结果。即，对于 N = 1、5、10、20、...、100、1000 或任何实际样本，运行 10000 次试验并绘制平均时间。如果你很幸运 X = 样本量，Y = 平均值。在该样本量下运行 10000 次的时间将绘制出一条漂亮的线、抛物线或一些易于建模的曲线。

因此，我不确定您是否需要有关（1）查找或编码算法或（2）分析它的帮助，您可能需要修改您的问题以指定这一点。

于 2012-05-21T00:50:32.770 回答
0 
P(x,y,z){
   1.print x
   2.if(y!=x)
   3. print y
   4.if(z!=x && z!=y)
   5.  print z
}

第 1 行：花费恒定时间c1 (c1:print x)

第 2 行：花费恒定时间c2（c2：条件测试）

第 3 行：花费恒定时间c3 (c3 :print y)

第 3 行：花费恒定时间c4（c4：条件测试）

第 4 行：花费恒定时间c5 (c5:print z)

分析 ：

除非您的函数 P(x,y,z) 不依赖于输入大小“r”，否则程序将花费恒定的时间来运行，因为Time Taken :T(c1)+T(c2+c3)+T(c4 +c5) ..总结函数 P(x,y,z) 的大 O 是O(1)，其中 1 是一个常数，表示自 T(c1),T(c2),.. 以来的恒定时间量T(c5) 都需要恒定的时间.. 并说如果函数 P(x,y,z) 从 1 迭代到 r.. 那么您的代码段的复杂性将会改变并且将根据输入大小即“r”

最佳情况：O(1)

平均情况：O(1)

最坏情况：O(1)

于 2013-11-19T09:50:57.697 回答