再问两道笔试题 （概率和排序）
本帖最后由 mkcing 于 2012-10-09 21:20:36 编辑 1，两个包甲包里800个红球，200个蓝球，乙包200个红球，800个蓝球，从甲乙两包中随机选出一个包。从此包中有放回的取球，共取11个，7红4蓝，问这个包是甲的概率
2，一个数组A，n个数，各不相同，则个数组每个元素都有一个性质，排序前，某元素的下标为index1,排序后此元素的下标为index2，这两个数的关系是 |index1 - index2| <= k << n。然后给这个数组排序，用选择排序的时间复杂度为O（kn）,题目要求是设计一个算法，时间复杂度小于O（kn）. 我没有想到更好的办法，只想到找出两个最值，用计数排序，用空间换时间，时间复杂度O（n）
[解决办法]
关于第一题我怎么感觉就应该是1/2，有限次取得的结果并不能影响甲乙两个包的随机性。
第二题，在选择排序的基础上可以做优化：1 O(n)时间获取最小值的index 2 更具
[解决办法]
index2-index1
[解决办法]
<=k,将左右的index划分成n/k的区域，对每个区域进行排序 3 合并每个区域排序后的结果，因为区域之间存在顺序关系，因此合并时间也是O(n/k) 这样总的时间复杂度应该为O(n)
