随机化

简介
　　randomization
　　在一组测定值中，每个测定值都是依一定的概率独立出现的，则称这一组测定值的出现是随机化的。可用游程检验来确定一组测定值的出现是否是随机化的。算法
　　在我们的生活中，人们经常会去掷色子来看结果，投硬币来决定行动，这就牵涉到一个问题：随机。
　　计算机为我们提供好了随机方法（部分计算器也提供了），那么对于有些具有瑕疵的算法，如果配上随机化算法的话，又是可以得到一样不到的结果。
　　定义：随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法，依赖于概率大小。
　　这种算法看上去是凭着运气做事，其实，随机化算法是有一定的理论基础的，我们可以想象，在[1,10000]这个闭区间里，随机1000次，随机到2这个数的几率是多大，何况1000次的随机在计算机程序中仅仅是一眨眼的功夫。可以看出，随机化算法有着广阔的前景。只是由于随机化算法比较难于掌控，所以并不是很多人都接触过他，但肯定有很多人都听说过。
　　下面，我们就随机化问题，举一个例子：
　　一个长度在4..10的字符串中，需要判定是否可以在字符串中删去若干字符，使得改变后字符串符合以下条件之一：
　　（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
　　例如：长度为6字符串“POPKDK”，若删除其中的“O”，“D”两个字母，则原串变为：“PPKK”，符合条件（2）AABB。
　　分析：
　　这道题很容易想到一种算法：运用排列组合：枚举每4个字母，然后逐一判断。算法是可行的，但是如果需要题目中加上一句话：需要判断n个字符串，且n<=100000，那么这样的耗时是不能让人忍受①的，因为在枚举的过程中，是非常浪费时间的。
　　(①：这里是指信息学中要求算法的普遍运算时间为：1000ms）
　　所以这道题有可能可以借助于随机化算法，下面我们来算一下在10个组符中取4个字符一共有多少种取法：C(4,10)=210。那么很容易得知，随机化算法如果随机100次，能都到的结果基本上就正确了，而随机时的时间消耗是O(1)，只需要判断没有随机重复即可，判重的时间复杂度也为O(1)，并且最多随机100次，这样就可以有效地得到答案，最大运算次数为：O(100n)，这是在计算机的承受范围内（1000ms）的。
　　从这里就能看出，随机化算法是一个很好的概率算法，但是它并不能保证正确，而且它单独使用的情况很少，大部分是与其他的算法：例如贪心、搜索等配合起来运用。
　　再举一个例子：
　　排序问题。快速排序是排序方法中较为便捷的方法之一，但是由于它极不稳定，最好的时候时间复杂度为O(n㏒n)，这里的㏒是指以2为底的对数运算。最坏的时候能达到与普通排序方法一样的O(n^2)。
　　而制约快速排序的有两个：一是数据，越无序的数据，快排的速度越快；二是中间点的枚举。
　　因为两个制约条件都与随机有着不可分开的关系。
　　所以，在快速排序中加入随机化算法无疑是十分重要的。运用
　　（1）数据读入时，随机排放数据位置。
　　（2）中间点的枚举进行多次随机化后决定。
　　这样就基本上将快速排序的时间复杂度维持在最好状态。

热门词条

应收账款区域货币区间估计 CPI（Consumer Price Index）资本成本单向定单金融危机认可外汇通汇率外汇佣金资产 ISO 经济增量成本服务 CFO MIT 加工什一税租赁期销售股价反弹 SME REF 抽签偿还 MG金融集团技术空头陷阱市场美元股利收入中小企业资本美国两会中国股市备付金率价格吊空指数股灾葡萄牙币 pt 调至市价清算下降三角形 Writer 电子汇兑 FDI 税粮 Theta width peg MACD 巴塞尔资本协议冲账艾略特波段理论的含义管理贴现现金流银行外汇交易法短期同业拆借拔档消费发展战略联系汇率制度延期付款汇票 Exposure 公司短期国际商业贷款阴烛金融中介理论不完全竞争市场理论 (金融) 标准普尔（S&P）美国贝勒大学正利差汇差清算率外汇分期付款汇票软通货出口物价指数选择权买方集中竞价百分比回撤无记名汇票最低报价戴维·凯特标准·普尔 500指数抵押品持平德国工业产值德国消费者物价指数成本协同效益非农就业人口交易德国伊弗研究所景气调查持平道琼斯公用事业平均指数金融指示汇票产品竞争力财务指标盈利能力比率 Quote 外汇实盘交易方式货币外汇实盘交易指令国际收支差额什么是外汇市场的过分反应 BBC制度货币期货交易南洋商业银行波浪理论与新闻价值性的关系希腊德拉马克

随机化

热门专栏

财联社

财华社

格隆汇

国际金融报

英为财情

嘉盛集团

香港智远

智通财经

热门词条