算法设计与分析 课件 9.1-概率算法 - 引例 - 主元素求解

算法设计与分析概率算法-引例信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版求一串数中的主元素，即出现次数超过一半的数1,2,2,3,2,4,2,4,2,2假设一定存在主元素方法一：排序，位置5的数即为主元素1222222344求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2方法二：士兵守阵地，留下的士兵就是主元素1223242422VS求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS1223242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS1223242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS23242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS23242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS23242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS2422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS2422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS2422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS22求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS22求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS22求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法三：上帝扔骰子，选择后再判断1223242422123456789103求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2方法三：上帝扔骰子，选择后再判断1223242422123456789102求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2求一串数中的主元素，即出现次数超过一半的数方法三：上帝投色子方法二：士兵守阵地方法一：排序确定算法概率算法允许算法执行过程中随机地选择计算步骤，因此算法的每一次执行过程可能都不完全相同。算法的每一计算步骤都是确定的，在输入不变的情况下，不管重复执行算法多少次，其结果都完全相同。确定算法：递归、分治、动规、贪心、搜索概率算法测试选择题：本节课针对主元素求解问题给出的三种方法：排序法，士兵守阵地和概率算法，三种算法在平均情况下需要的计算次数分别表示为W1，W2和W3，三者从大到小排序正确的是（）A：W1，W2，W3