这个算法的时间分析怎么算?随机产生n个自然数,要求各不相同,这个的一个算法为,数保存在数组里,每个随机产生,如果已经存在就重来,怎么计算此算法的时间期望?因为步骤不定,完全无从下手啊,求大神.可能我没说清楚,如n为5,则产生1到5的任意排列,如用此算法,产生最后一个的概率为0.2,步骤难确定
问题描述：
这个算法的时间分析怎么算?
随机产生n个自然数,要求各不相同,这个的一个算法为,数保存在数组里,每个随机产生,如果已经存在就重来,怎么计算此算法的时间期望?因为步骤不定,完全无从下手啊,求大神.
可能我没说清楚,如n为5,则产生1到5的任意排列,如用此算法,产生最后一个的概率为0.2,步骤难确定
答
1、定义一个数组
2、产生一个随机数
3、把产生的随机数按递增顺序放入数组,如果已经存在则舍弃该数据
4、重复2和3,产生需要数目的随机数
如果需要的数据不是很多的话,时间复杂度是O（n）