【免费】第一章绪论作业-第一次作业1资源-CSDN文库

需积分: 0 34 浏览量 2022-08-08 21:21:30 上传评论收藏 13KB DOCX 举报

资源详情

资源评论

资源推荐

一、写出如下程序中各语句的频度。

(1) 9

(2) 9

(3) 2

(4) 2

(5) 9

(6) 45

(7) 45

(8) 18

(9) 18

二、有如下程序段：

if 语句执行了多少次？ 1100

y--执行了多少次? 100

x ++执行了多少次? 1000

三、书中 16 页的起泡排序如下：

1.分析该算法的最佳情况，最坏情况和平均情况下各自的时间复杂度（给出分析思路与过

程）。

最佳情况:

最佳情况即给定整数序列已经为自小至大的有序数列，即时间复杂度为 T(n)=O（0）

最坏情况:

最坏情况为当给定整数序列是按照从大到小排列的有序数列，此时，基本操作的执

行次数为 n(n-1)/2，则其时间复杂度为 T(n)=O（n^2）

平均情况:

假设 a 中初始输入数据可能出现 n!种的排列情况的概率相等，则起泡排序的平均

时间复杂度为 T(n)=O（n^2）

2.比较与 C 语言书中的起泡排序异同，并从时空效率角度说明谁更优。

该书中冒泡排序与 C 语言书中相比，主要多了一个判断是否产生值交换的 CHANGE

变量。

相比 C 语言书中的冒泡排序，当给定序列和算法相比是正向有序数列时，数据结构

书中的算法在进行一次比较后就会跳出外层循环，其基本操作执行次数为 0。

在这种情况下，算法的时间复杂度为 T(n)=O（n）

而 C 语言书中的冒泡排序，如果给定数列和算法相比为正向有序数列，算法仍然会

进行 n^2 次比较后，才会结束循环。这种情况下，算法的时间复杂度仍然

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论0

内容反馈

王元祺

粉丝: 65
资源: 303

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip