计算机问题求解一论题2-8 -概率分析与随机算法 2018年04月24日
计算机问题求解 – 论题2-8 - 概率分析与随机算法 2018年04月24日
HIRE-ASSISTANT(n) 1 best =0 /candidate 0 is a least-qualified dummy candidate 2 for i 1ton 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 那么，有没有问： 般情况下，代价 问题3： 会如何？ 这个算法是“确定”的吗？ 什么是“随机”的呢？ 它的best和worst case是什么？
那么，有没有问： 一般情况下，代价 会如何？
Average-Case Analysis of Algorithms We focus on computing the running time of various algorithms. When the running time of an algorithm is different for different inputs of the same size,we can think of the running time of the algorithm as a random variable on the sample space of inputs,and thus,we can analyze the expected running time of the algorithm.This gives us an understanding different from studying just the worst-case running time for an input of a given size
Average-Case Analysis of Algorithms
Average case Analysis of an Algorithm In order to perform a probabilistic analysis,we must use knowledge of,or make assumptions about,the distribution of the inputs. Then we analyze our algorithm,computing an average-case running time,where we take the average over the distribution of the possible inputs.Thus we are,in effect,averaging the running time over all possible inputs.When reporting such a running time,we will refer to it as the average-case running time
Average case Analysis of an Algorithm
HIRE-ASSISTANT (n) 1 best =0 /candidate 0 is a least-qualified dummy candidate 2 for i 1ton 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 问题4： 在hiring problem算法中假设应 聘者随机到达”意味着什么？