发布资金信息 发布项目融资 申请上市辅导 发布金融峰会 发布文章资讯
  • 首页
  • 找项目
  • 找资金
  • 金融人才网
  • 金融峰会
  • 金融学院
  • 投融资俱乐部
  • 网站会员服
  • 随机化

       时间:2018-04-25 22:32:51     浏览:57    评论:0    
    核心提示:简介  randomization   在一组测定值中,每个测定值都是依一定的概率独立出现的,则称这一组测定值的出现是随机化的。可用游程检验来确定一组测定值的出现是否是随机化的。算法  在我们的生活中,人们经常会去掷色子来看结果,投硬币来决定行动,这就牵涉到一个问题:随机。  计算机为我们提供好了随机方法,那么对

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

    推荐图文
    推荐金融学院
    点击排行
    关于我们 | 组织结构 | 企业文化 | 办公环境 | 经营动态 | 管理团队 | 行为准则 | 投资策略 | 投资保障 | 风险控制 | 联系我们 | 微信群
    广告合作 | 友情链接 | 网站地图 | RSS订阅
    Copyright © 2006-2021 投融网 Inc. All rights reserved.
    ICP备案号:粤ICP备16012416号
    联系我们
    QQ咨询
    电话咨询
    email
    在线留言
    微信联系
    返回顶部