算法设计与分析 实验一 排序算法性能分析(上)

简介: 算法设计与分析 实验一 排序算法性能分析(上)

一、实验目的与要求


1、实验基本要求


①掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理

②掌握不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。


2、实验亮点


①除了基本五种排序算法,额外选择了基数排序,希尔排序和堆排序三种排序算法进行性能分析并对一些算法提出优化方案。

②使用Tableau进行绘图,完成数据可视化

③对实验过程中发现的相关问题进行了探究并解决

④分析了每一种情况下理论时间消耗与实际时间消耗偏差的原因。

⑤实现了对部分算法的优化以及思考题对一万亿数据的排序问题


二、实验内容与方法


 排序问题要求我们按照升序排列给定列表中的数据项,目前为止,已有多种排序算法提出。本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理,并进行代码实现。通过对大量样本的测试结果,统计不同排序算法的时间效率与输入规模的关系,通过经验分析方法,展示不同排序算法的时间复杂度,并与理论分析的基本运算次数做比较,验证理论分析结论的正确性。


三、实验步骤与过程


(一)独立算法性能分析


1. 冒泡排序


(1)算法实现原理

①比较相邻的元素。如果第一个比第二个大,就交换他们两个。

②对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

③针对所有的元素重复以上的步骤,除了最后一个。

④持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。


 下面以使用冒泡排序3,5,1,2这四个数字为例,以图示介绍冒泡排序,见下图


1a6c8a656f7e4c42933b1be69d149ca1.png


(2)源代码


BUBBLESORT(A)
  for i = 1 to A.length-1
    for j = A.length downto i + 1
      if A[j] < A[j - 1]
        exchange A[j] with A[j - 1]


(3)算法性能分析:

①时间复杂度分析:

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值


5d3d503570a54fcdb33b426a6ed52acd.png


所以,冒泡排序最好的时间复杂度为O ( n )

若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较( 1 ≤ i ≤ n − 1 ) ,且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:


53b220de13e04e3b96ccccb7a42f5472.png


冒泡排序的最坏时间复杂度为O ( n 2 )

综上,因此冒泡排序总的平均时间复杂度为O ( n 2 )


②数据测试分析:

使用随机数生成器生成了从102106的不同数据量级的随机数,通过使用冒泡排序进行排序并获取了程序运行时间。为降低偶然性,对20组数据取平均值,选择105 时运行时间为理论值并做表如下:

976bfb6aa97f454baf9544596c1903b8.png

通过获得的数据,使用 105

时的时间消耗为基准理论值,使用Tableau做图像并拟合如图:

e29ccdf79a7a41ccba7c503926b01484.png

  由于冒泡排序算法时间复杂度为O (n2 )  ,故,数量级扩大10倍时,时间消耗应扩大100倍。由上图,可得随着数据量的增大,拟合效果越好,所有实验数据符合O ( n 2 )  )的时间复杂度。

 从上图可知,实际时间消耗曲线与理论时间消耗基本拟合,冒泡排序算法的时间复杂度满足O (n2 )


2. 选择排序


(1)算法实现原理

①首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

②从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾。

③重复上述过程直至所有元素均排序完毕。


下面以使用选择排序3,5,1,2这四个数字为例,以图示介绍选择排序,见下图

e552b4a7b46142c98e5863612ee8a13d.png


(2)源代码

SELECTSORT(ele)
  for i=0 to n-2
    min=i
    for j= i+1 to n-1
        if ele[min]>ele[j]  min=j
    swap(ele[i],ele[min])

(3)算法性能分析

①时间复杂度分析:

选择排序的交换操作介于0 00与n − 1次之间。选择排序的比较操作为n ( n − 1 ) / 2  次之间。选择排序的赋值操作介于 0 和 3 ( n − 1  次之间。比较次数为O ( n2 )

)。比较次数与关键字的初始状态无关,总的比较次数N = ( n − 1 ) + ( n − 2 ) + . . . + 1 = n ( n − 1 ) / 2 交换次数O ( n ),最好情况是,已经有序,交换0次;最坏情况交换n − 1 次,逆序交换n / 2 次。因此选择排序的时间复杂度为O ( n2 )


②数据测试分析:

使用随机数生成器生成了从102106的不同数据量级的随机数,通过使用选择排序进行排序并获取了程序运行时间。为降低偶然性,对20组数据取平均值,选择105时运行时间为理论值并做表如下:

ea188ee6d28d4e44a86d2eb34f678591.png

通过获得的数据,使用105 时的时间消耗为基准理论值,使用Tableau做图像并拟合如图:


f731f27573bd40b08e23ffa565aa848f.png


由于选择排序算法时间复杂度为O (n2 ),故,数量级扩大10倍时,时间消耗应扩大100倍。由上图,可得随着数据量的增大,拟合效果越好,所有实验数据符合O (n2 )的时间复杂度。

从上表和上图中可以发现整体时间消耗都大致满足数量级扩大10倍,时间消耗扩大100倍的规律。但对于101102

数量级时存在较大误差,拟合效果较差。通过分析可知,选择排序中进行了很多次相互调换元素(相互赋值)的操作,从而造成了时间浪费。我进行了如下两次对比实验,使用库函数swap和手写调换元素的函数进行对比,可以发现,使用swap函数的小数据拟合效果要明显好于手写。因此,小数据下,较差的拟合效果是因为较多次交换占用了更多时间,当数据较小时,数据交换造成的时间损耗更明显。但当数据变多时,这种影响被冲淡,故拟合效果比较好。


3. 插入排序


(1)算法实现原理

①假设前面n − 1(其中n ≥ 2 )个数已经有序的,现将第n个数插到前面有序序列中,并找到合适位置,使得插入第n 个数后仍为有序序列

②按照此法对所有元素进行插入,直至整个序列为有序序列


(2)源代码


INSERTION-SORT(A)
    for j=2 to A.length:
        key=A[j]
        //将A[j]插入已排序序列A[1..j-1]
        i=j-1
        while i>0 and A[i]>key
            A[i+1]= A[i]
            i=i-1
        A[i+1]=key

下面以使用插入排序3,5,1,2这四个数字为例,以图示介绍插入排序,见下图


e61ef10bb71f416fb2d35656d77bf6c7.png


(3)算法性能分析

①时间复杂度分析

在插入下标为i的元素的时候(假设该元素为x xx),R0,R1,R2,Ri-1

已经有序了,那么x 实际上有n + 1个备选位置可以插入,按照独立分布来说,每个位置的概率都是89b450b1602540f68d1c0cf63b8117f5.png,那么这n + 1 n+1n+1个位置从左到右对应的比较次数为( i , i , i − 1 , . . . , 1 )。那么我们就可以得到一趟插入排序的平均时间复杂度为

image.png

因此,插入排序的时间复杂度为O (n2)


②数据测试分析

使用随机数生成器生成了从102102  的不同数据量级的随机数,通过使用插入排序进排序并获取了程序运行时间。为降低偶然性,对20组数据取平均值,选  105时运行时间为理论值并做表如下:

cc94f33dd70b4398946f7b1c90096d1d.png


通过获得的数据,使用105 时的时间消耗为基准理论值,使用Tableau做图像并拟合如图:


eefe2d0861694e1c850941cd9b6b6b6a.png


由于插入排序算法时间复杂度为O ( n 2 ),故,数量级扩大10倍时,时间消耗应扩大100倍。由上图,可得随着数据量的增大,拟合效果越好,所有实验数据符合O ( n 2 ) 的时间复杂度。

从上表和上图中可以发现整体时间消耗都大致满足数量级扩大10倍,时间消耗扩大100倍的规律。但对于101102  数量级时存在较大误差,拟合效果较差。通过分析可知,插入排序中进行了对需插入元素的保存操作,当数据较小时,较差的拟合效果是因为每次对插入前数值的保存占用的时间比例较大。当数据较小时,数据交换造成的时间损耗更明显。但当数据变多时,这种影响被冲淡,故拟合效果比较好。


4. 快速排序


(1)算法实现原理

①首先设定一个分界值,通过该分界值将数组分成左右两部分。

②将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。

③然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

④重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。


下面以使用快速排序11,8,3,9,7,1,2,5这八个数字为例,以图示介绍快速排序,见下图


ad4c5987d66840b298423ac48643567c.png


(2)源代码


QUICKSORT(SeqList R,int low,int high)
  int pivotpos;//划分后的基准记录的位置
  if(low<high)
    //仅当区间长度大于1时才需排序
    pivotpos = Partition(R,low,high);
    //对R[low...high]进行划分
    QuickSort(R,low,pivotpos-1);
    QuickSort(R,pivotpos+1,high);


(3)算法性能分析

①时间复杂度分析:

快速排序的一次划分算法从两头交替搜索,直到low和high重合,因此其时间复杂度是O ( n ) ;而整个快速排序算法的时间复杂度与划分的趟数有关。

最理想的情况是,每次划分所选择的中间数恰好将当前序列几乎等分,经过log ⁡ n 趟划分,便可得到长度为1的子表。这样,整个算法的时间复杂度为O ( n log ⁡ n )

最坏的情况是,每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子表中一个为空表,另一子表的长度为原表的长度-1。这样,长度为n nn的数据表的快速排序需要经过n nn趟划分,使得整个排序算法的时间复杂度为O ( n 2 )

综上快速排序的平均时间复杂度也是O ( n log ⁡ n )

②数据测试分析:

使用随机数生成器生成了从101106

的不同数据量级的随机数,通过使用快速排序进行排序并获取了程序运行时间。为降低偶然性,对20组数据取平均值,选择105时运行时间为理论值并做表如下


02020ce4dcd4418780ccce6caa7cf053.png

通过获得的数据,使用105 时的时间消耗为基准理论值,使用Tableau做图像并拟合如图



88d18833813b41fba72cf8d81da03cbb.png


结合上表和上图不难得出:整体时间消耗都大致满足O ( n log ⁡ n )的时间复杂度,且数据量越大拟合效果越好。

从上表和上图中可以发现整体时间消耗都大致满足时间复杂度。但对于101102,数量级时存在较大误差,拟合效果较差。通过分析可知,快速排序中开辟申请空间与递归栈都会影响运行性能和运行时间。当数据较小时,这种影响造成的时间损耗更明显。但当数据变多时,开辟空间与递归栈对时间的影响被冲淡,故拟合效果比较好。

相关文章
|
29天前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
53 4
|
27天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
20 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
12天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
27天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
17 0
数据结构与算法学习十四:常用排序算法总结和对比
|
19天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
2月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
在 Python 编程中,算法的性能至关重要。本文将带您深入了解算法复杂度的概念,包括时间复杂度和空间复杂度。通过具体的例子,如冒泡排序算法 (`O(n^2)` 时间复杂度,`O(1)` 空间复杂度),我们将展示如何评估算法的性能。同时,我们还会介绍如何优化算法,例如使用 Python 的内置函数 `max` 来提高查找最大值的效率,或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外,还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践,您将能更高效地优化 Python 程序。
51 4
|
25天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
2月前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
37 1
|
27天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
2月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
111 19