0

谁能用简单的话解释算法的概率分析？在 Wiki 页面中找不到太多信息。

4

3 回答 3

2

假设您要确定基于比较的排序算法的预期运行时间。以下是解决此问题的方法：

  • 定义算法所有可能输入的分布
    • 例如，说所有 N! 排序 N 个不同数字的排列同样可能（1/N！）
  • 确定每个可能输入的运行时间
  • 通过对所有可能的输入求和输入的概率乘以输入的运行时间来 计算预期运行时间
    • 也就是说，E[Runtime] = sum i=1,...,N! { P(i) * 运行时(i) } = 总和i=1,...,N! {运行时（i）}/N！

例如，如果您使用快速排序算法（简单地选择枢轴）执行此操作，您会发现快速排序的预期运行时间为 O(N log N)，而最坏情况的运行时间为 O(N 2 )。

于 2013-08-14T18:12:57.800 回答
0

我发现了一个很棒的演示文稿，它用简单的术语解释了这一点

http://www.lsi.upc.edu/~conrado/research/talks/survey-Stellenbosch.pdf

恕我直言，它归结为“给定算法和“典型输入”随机算法的性能是什么”

其中，典型输入实际上取决于您评估算法的目的，您可以为输入值提供均匀或随机分布并测量性能特征

于 2013-08-14T09:31:12.383 回答
0

用简单的语言：

如果你想煮牛排，你会知道牛排的大小会改变烤架上烤好的时间。生牛排是您的输入，烤架是您的功能（即算法），熟牛排是您的输出。

现在，假设我问你：“你的烤架平均烤一块牛排需要多少时间？” 你会怎么做呢？概率分析表明，所有可能大小的牛排都可能适合您。因此，此方法会产生平均运行时间。此方法将为您提供一个代表这种情况的数字，因此您可以比较不同的烤架。希望有帮助！

于 2017-02-04T20:21:42.063 回答