计算机问题求解一论题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算法中假设应 聘者随机到达”意味着什么？
HIRE-ASSISTANT(n) 1 best =0 /candidate 0 is a least-qualified dummy candidate 2 fori 1ton 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 问题5： 在niring problem算法中分析算 法所需要的随机变量是什么？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： 。Hiring操作执行次数：X E[X]=∑xPr{X=x t= 这个公式的计算，难在哪里？ 观察到这个问题其实是在分析（甚至是统计）重 复独立试验，能否简化？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： • Hiring操作执行次数：X 这个公式的计算，难在哪里？ 观察到这个问题其实是在分析（甚至是统计）重 复独立试验，能否简化？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： 。·Hiring操作执行次数：X; 0 事件“第个候选人被雇用”的indicator::X,; X=X1+X2+…+Xm E[X] (by equation(5.2)) ∑EXI (by linearity of expectation) i= n (by equation(5.3)) E[x]=1/i i= Inn +0(1)(by equation (A.7)). 为什么？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： • Hiring操作执行次数：X ； • 事件“第i个候选人被雇用”的indicator：Xi ; 为什么？
基于概率的算法分析与随机算法 ·输入数据的概率模型 outcomes,sample space,probability probability variant 口通过分布、期望来进行平均时间开销分析 ·难以给出概率模型时： 口“制造”一个随机分布，进而利用这个随机分布进行概率分析
基于概率的算法分析与随机算法 ◼ 输入数据的概率模型 ❑ outcomes，sample space，probability ❑ probability variant ❑ 通过分布、期望来进行平均时间开销分析 ◼ 难以给出概率模型时： ❑ “制造”一个随机分布，进而利用这个随机分布进行概率分析
随机算法 RANDOMIZED-HIRE-ASSISTANT(n) randomly permute the list of candidates 2 best =0 /candidate 0 is a least-qualified dummy candidate 3 for i 1to n 4 interview candidate i 5 if candidate i is better than candidate best 6 best i 7 hire candidate i 相当于用抛硬币或 算法的执行不再依赖 者掷色子的方式决 于输入数据，关键取 定下一步该干什么！决于一个“随机数” 这个随机现像，我们可以清楚认识它的班率模型
随机算法 相当于用抛硬币或 者掷色子的方式决 定下一步该干什么！ 算法的执行不再依赖 于输入数据，关键取 决于一个“随机数” 这个随机现象，我们可以清楚认识它的概率模型