随机数值算法 计算值 k=0; for i=1 to n do 随机地产生四边形中的一点(x,y); ifx2+y2≤1then k=k+1; return(4k)/n; 时间复杂性=O(n),n是随机样本的大小 解的精确度随着随机样本大小n增加而增加 11
随机数值算法 ◼ 计算值 k=0; for i=1 to n do 随机地产生四边形中的一点(x, y); if x 2+y21 then k=k+1; return (4k)/n; ◼ 时间复杂性=O(n)，n是随机样本的大小 ◼ 解的精确度随着随机样本大小n增加而增加 11
随机数值算法 计算积分g(x)dx 强大数定律 >假定{s(x)}是相互独立同分布的随机变量序列,如果 它们有有限的数学期望E(s(x)=a,则 n→∞n o计算积分 独立同分布 >令f(x)=1/(b-a)为概率密度函数,a≤x≤b >{s(x)}为离散随机变量,期望E(s(x)=s(x)f(x) >{s(x)}若为连续型的,期望E(s(x)=s(x)f(x)dx 令g(x)=s(x)f(x),则期望E(s(x)=ng(x)dx 12
随机数值算法 ��计算积分◼ 𝒃 𝒈 𝒙 𝒅𝒙 强大数定律 ➢ 假定{s(x)}是相互独立同分布的随机变量序列，如果 它们有有限的数学期望E(s(x))=a，则 lim 𝒏→∞ 𝟏 𝒏 σ𝒊=𝟏 𝒏 𝒔(𝒙𝒊) = 𝐚 = 𝐄(𝐬 𝐱 ) 计算积分 ➢ 令f(x)=1/(b-a)为概率密度函数，a x b ➢ {s(x)}为离散随机变量, 期望𝐄(𝒔 𝒙 ) = σ 𝒔 𝒙 𝒇(𝒙) ➢ {s(x)}若为连续型的，期望𝐄 𝒔 𝒙 = �� 𝒃 𝒔 𝒙 𝒇(𝒙)𝒅𝒙 ➢ 令g(x)=s(x)f(x)，则期望𝐄 𝒔 𝒙 = �� 𝒃 𝒈(𝒙)𝒅𝒙 12 独立同分布
随机数值算法 计算积分g(x)dx 强大数定律 n→∞n 计算积分 >令g(x)=s(x)f(x),则期望E(s(x)=g(x)dx (x)dx =E((x) lim --1s(xi) n→∞n lim -2[(xi)/(xi) b-aon n→ni=19(xi 13
随机数值算法 ��计算积分◼ 𝒃 𝒈 𝒙 𝒅𝒙 强大数定律 ➢ 𝐥𝐢𝐦 𝒏→∞ 𝟏 𝒏 σ𝒊=𝟏 𝒏 𝒔(𝒙𝒊) = 𝐚 = 𝐄(𝐬 𝐱 ) 计算积分 ➢ 令g(x)=s(x)f(x)，则期望𝐄 𝒔 𝒙 = �� 𝒃 𝒈(𝒙)𝒅𝒙 �� ➢ 𝒃 𝒈(𝒙)𝒅𝒙 = 𝐄 𝒔 𝒙 = 𝐥𝐢𝐦 𝒏→∞ 𝟏 𝒏 σ𝒊=𝟏 𝒏 𝒔(𝒙𝒊) ➢ = 𝐥𝐢𝐦 𝒏→∞ 𝟏 𝒏 σ𝒊=𝟏 𝒏 𝒈(𝒙𝒊)/𝒇(𝒙𝒊) ➢ = 𝐥𝐢𝐦 𝒏→∞ 𝒃−𝒂 𝒏 σ𝒊=𝟏 𝒏 𝒈(𝒙𝒊) 13
随机数值算法 计算积分g(x)dx oR=0; o for i=1 to n do 随机产生[a,b]中点 R=R+g(x) o return (b-a)*R/n 时间复杂性=(n),n是随机样本的大小 解的精确度随着随机样本大小n增加而增加 14
随机数值算法 ��计算积分◼ 𝒃 𝒈 𝒙 𝒅𝒙 R=0; for i=1 to n do 随机产生[a, b]中点x; R=R+g(x); return (b-a)*R/n ◼ 时间复杂性=O(n)，n是随机样本的大小 ◼ 解的精确度随着随机样本大小n增加而增加 14
第k小元素(Las Vegas) 输入:S={x1,x2xn},整数k,1≤k≤n. 输出:S中第k小元素 15
第k小元素(Las Vegas) ◼ 输入：S={x1 , x2 , …, xn }，整数k，1kn. ◼ 输出：S中第k小元素. 15