数据结构实验报告_实验四1
需积分: 0 49 浏览量
2022-08-03
19:48:43
上传
评论
收藏 429KB PDF 举报
数据结构实验报告
姓名： 杨家玺 学号：U201717007 班级：软工 1703 班
2018．12．08
实验四
基于桶式排序的基数排序的影响因素、后缀表达式的转换
一、实验描述
1. 实现桶式排序和基于桶式排序的基数排序。在基数!，数组长度"和最大元素值#中，
对排序时间影响最大的是哪一个?元素在未排序数组中的顺序是否对时间复杂度有影响?
设计试验证明你的想法
2. 用 C 语言设计堆栈，并实现中缀表达式到 后缀表达式的转换
二、实验环境
1. 开发环境： OS X
2. IDE： VSCode
3. 编译器： Clang 9.1.0 Apple LLVM
4. C 标准： C11
三、问题分析
1. 排序与分析
桶式排序与基数排序的原理不再赘述，下文主要针对影响基数排序性能的三个变量
进行讨论与分析，并编写程序验证分析的正确性。
从桶式排序的代码可以看出，代码的主循环进行$次，$是在!进制下最大值#的位
数，例如! % &'( # % ))** + ,$ % -,,./,,! % &)( # % 0**1223 + ,$ % 0,，在每次循环
中先初始化!个桶的内容，然后将桶内元素全部倒出，这一过程花费时间41! 5 "3，"
为数据量。
所以桶式排序的时间复杂度为6 !( "( # % 411" 5 !3 7 89:
;
#3，当" < !时，有
6 !( "( # % 41! 7 89:
;
#3
A. !( "( #的变化对61!( "( #3的影响。
令
= % " 5 ! 7 89:
;
# %
>?@
>?;
7 1" 5 !3
AB,,
C=
C"
%
>?@
>?;
AAB,,
C=
C!
% D
>?@
;7 >?;
E
7 " 5 ! 5
>?@
>?;
%
>?@
;7 >?;
E
7 ! 7 8F! D ! D "
AAAB,,
C=
C#
%
GH;
@7>?;
首先，对于I，考察=对I偏导的正负性
令导数大于'， ! 7 8F! D ! D " J '
变形：! 7 8F! J ! 5 "K"
考虑到现实中数据量"远大于排序基数!，所以认为这个不等式在正常情况下不可能
成立，故认为!的增长会使=下降。
对于#和"，比较两个偏导数的大小：
评论0