知识卡片
插入排序最坏移动数求和
在逆序输入等最坏情形,第j轮要把前面j项右移。对n项,移动次数是1+2+…+(n−1)=n(n−1)/2,所以在每次比较/移动按常数计的模型下为平方量级。
例如4项的最坏移动数为1+2+3=6,这是按公式展开的教学数值,不是实测。原文外循环、内循环描述有变量混乱,应按issort代码j从1到size−1、i向左递减理解。
若元素字节数或比较器本身成本随另一个参数变化,不能仍把每次操作无条件当常数;这条分析首先针对固定元素成本的模型。
207最坏前缀每次需全遍历,总右移/比较主项n(n−1)/2。原文“递增排序时O(n)”应限定输入已经按所需递增顺序有序,此时每次检查即停;仅选择递增方向并不保证线性。固定元素/比较成本前提仍需说明。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
1到n-1累加和的过程,求和的结果为:T(n)=(n(n+1)/2)-n,从结果看得出消耗了一定量的时间。(这个等式来源于著名的从1到n的求和公式。)结果如下: 示例4-1:第12章中实现的插入排序
- · 查看原书依据
从1到n-1数据的和,即运行时间T(n)=(n(n+1)/2-n,乘以一段固定时间。(这是由1到n的著名求和公式推导出来。)用O-表示法可以简化为O(n2)。当在递增排序中使用插入排序时,其时间复杂度为O(n)。插入排序不需要额外的空间,因此它只使用无序数据本身的存储空间即可。 示例12-1:插入排
参考来源
- 位置:《算法精解:C语言描述》第4章《实例分析:插入排序》(spine1201;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1169.html;u044-ch04-007)。
- 结论依据:44求和说明、02695公式和02696-02697真实循环,直接核对n(n−1)/2;4项为小数字演算,补明确按固定元素成本计数。
- 原始内容:1到n-1累加和的过程,求和的结果为:T(n)=(n(n+1)/2)-n,从结果看得出消耗了一定量的时间。(这个等式来源于著名的从1到n的求和公式。)结果如下: 示例4-1:第12章中实现的插入排序
- 位置:《算法精解:C语言描述》第12章《插入排序的实现与分析》(spine1339;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1305.html;u207-ch04-007)。
- 结论依据:207最坏前缀每次需全遍历,总右移/比较主项n(n−1)/2。原文“递增排序时O(n)”应限定输入已经按所需递增顺序有序,此时每次检查即停;仅选择递增方向并不保证线性。固定元素/比较成本前提仍需说明。
- 原始内容:从1到n-1数据的和,即运行时间T(n)=(n(n+1)/2-n,乘以一段固定时间。(这是由1到n的著名求和公式推导出来。)用O-表示法可以简化为O(n2)。当在递增排序中使用插入排序时,其时间复杂度为O(n)。插入排序不需要额外的空间,因此它只使用无序数据本身的存储空间即可。 示例12-1:插入排