算法导论第九章中值和顺序统计.ppt

该【算法导论第九章中值和顺序统计 】是由【54156456】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【算法导论第九章中值和顺序统计 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法导论第九章中值和顺序统计目录中值和顺序统计快速选择算法堆排序算法线性时间选择算法CONTENTS01中值和顺序统计CHAPTER中值是一组数据排序后处于中间位置的数值。总结词中值是一组数据中排序后位于中间位置的数值,它反映了数据的集中趋势。当数据量是奇数时,中值是中间位置的数值;当数据量是偶数时,中值是中间两个数值的平均值。中值可以用来衡量数据的偏度和峰度,以及识别异常值。详细描述中值定义顺序统计量定义总结词顺序统计量是一组数据按照大小排序后,位于特定位置的数值。详细描述顺序统计量是指一组数据按照大小排序后,位于特定位置的数值。例如,最小值、最大值、第1百分位数、第25百分位数、第50百分位数、第75百分位数和第99百分位数等都是常见的顺序统计量。这些统计量可以帮助我们了解数据的分布情况,以及数据在不同位置的特征。总结词中值和顺序统计在数据分析、统计学、医学、金融等领域有广泛应用。详细描述中值和顺序统计是数据分析中的基本概念,广泛应用于统计学、医学、金融等领域。在统计学中,中值和顺序统计量可以帮助我们了解数据的分布特征,进行数据分组和异常值检测等。在医学中,中值和顺序统计可以用来分析生命体征数据、药物疗效等。在金融中,中值和顺序统计可以用来分析股票价格、收益率等金融数据,进行风险管理、投资组合优化等。此外,中值和顺序统计还可以用于其他领域的数据分析,如社会学、地理学等。中值和顺序统计的应用场景02快速选择算法CHAPTER利用分治策略快速选择算法基于分治策略,将待处理的数据集划分为若干个子集,然后递归地在子集上应用快速选择算法,最后将结果合并以确定中值或顺序统计值。随机化思想在划分数据集时,快速选择算法采用随机化的方法,使得每次划分的子集大小相近,从而减少递归的次数,提高算法的效率。快速选择算法的原理从待处理的数据集中随机选择一个元素作为枢轴元素。随机选择一个枢轴元素将数据集划分为子集递归处理子集返回结果将数据集划分为两个子集,一个子集包含比枢轴元素小的元素,另一个子集包含比枢轴元素大的元素。对划分的两个子集分别递归地应用快速选择算法,以确定中值或顺序统计值。根据递归返回的结果,确定整个数据集中值的位置。快速选择算法的步骤123在最坏情况下,快速选择算法的时间复杂度为O(n),其中n为数据集的大小。最坏情况下的时间复杂度通过随机化方法,快速选择算法在平均情况下的时间复杂度为O(n/2),即O(logn)。平均情况下的时间复杂度快速选择算法的空间复杂度为O(logn),其中n为数据集的大小。空间复杂度快速选择算法的时间复杂度分析