E=MC2的日志 - 鱼C论坛 - Powered by Discuz!

设为首页收藏本站

切换到窄版

鱼C论坛 › E=MC2 › 日志

E=MC2

https://fishc.com.cn/?266894

数据结构与算法|

分享用O(nlgk)时间查找k分位数: 2014-3-17 18:44; 相关问题： The kth quantiles of an n-element set are the k 1 order satatistics that divide the sorted set into k equal-sized sets(to within 1).Give an O(nlgk)time algorithm to list the kth quantiles of a set. 对一个含有n个元素的集合来说，所谓k分位数（the kth quantile），就是 ...; 个人分类: 数据结构与算法|877 次阅读|0 个评论

分享找出集合S最接近中位数的k(k≤n)个数: 2014-3-17 18:39; 相关问题：给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k≤n后，它能确定出S中最接近其中位数的k个数. 思考过程：如果给出在线性时间内的算法，那么可能要用到最坏为线性时间的查找第i小元素的子程序SELECT。我们先找到这n个数的中位数，然后以此中位数为中心，左边距离中位数k/2 ...; 个人分类: 数据结构与算法|960 次阅读|0 个评论

分享最坏情况快速排序的运行时间为Ο(nlgn)的算法: 2014-3-14 09:47; 思想方法与思考过程：快速排序对主元的划分决定了其运行时间，如果最坏是Ο(nlgn)，那么就不允许出现极端划分情况。因为我们学习了最坏时间了线性的选择算法，我们何不利用其每次选择都选中位数作为主元的方法来避免极端情况的发生？既然每次都选择中位数作为主元，那么其递归运行时间总是T(n)=2T(n/2)+Ο(n) 这样 ...; 个人分类: 数据结构与算法|877 次阅读|0 个评论

分享最坏为线性时间的查找第i小元素: 2014-3-14 09:42; 思想方法：既然是线性时间查找元素，那么我们每次划分时都需要均衡划分。所以我们每次总是取中位数辅助数组B的中位数x为原数组A的主元进行划分。该算法分5步： 1.将输入数组的n个元素划分为floor(n/5)组，每组5个元素，且至多只有一个组由剩下的nmod5元素组成。 2.寻找ceil(n/5)个组中每一组的中位数。首 ...; 个人分类: 数据结构与算法|895 次阅读|0 个评论

分享算法导论第九章课后答案: 2014-2-6 10:55; 9.1-1 证明：在最坏情况下，找到n个元素中第二小的元素需要n+向上取整lgn-2次比较。我们对于查找第2小元素分成2步。 step1:我们先将数组中的元素两两成对比较，共需n/2次比较，那么就有n/2个元素是较小的元素，然后再将这些较小的元素再次两两成对比较，又淘汰一半，重复这样的循环，每次淘汰一半元素直到只剩下1个 ...; 个人分类: 数据结构与算法|4709 次阅读|0 个评论

分享算法导论第八章思考题: 2014-1-27 09:53; 8-1(比较排序的概率下界) 在这一问题中，我们将证明对于给定的n个互异的输入元素，任何确定或随机的比较排序算法，其概率运行时间都有下界Ω(nlgn)。首先分析一个确定的比较排序算法A，其决策树为Ta，假设A的输入的每一种排列情况都是等可能的。 a) 假设Ta的每个叶子结点都标有在给定的随机输入情况下到达该结点的 ...; 个人分类: 数据结构与算法|2308 次阅读|0 个评论热度 2

分享算法导论第八章线性时间排序课后答案: 2014-1-19 21:09; 8.1排序算法的下界 8.1-1 在一颗比较排序算法的决策树中，一个叶结点可能的最小深度是多少？最少进行n-1次比较，所以深度最小是n-1 8.1-2不用斯特林近似公式，给出lg(n!)的渐近紧确界，利用A.2节介绍的技术来求累加和∑lgk. ∫(lgk)dk=klgk-∫kd(lgk)=klgk-(1/ln2)k 所以∑lgk=(nlgn-1lg1)-(1 ...; 个人分类: 数据结构与算法|3958 次阅读|0 个评论

分享算法导论第七章课后答案: 2014-1-9 20:02; 7.1-1 参照图7-1的方法，说明PARTITION在数组A={13,9,9,5,12,8,7,4,21,2,6,11}上的操作过程。 A={13,19,9,5,12,8,7,4,21,2,6,11} ={13,19,9,5,12,8,7,4,21,2,6,11} ={13,19,9,5,12,8,7,4,21,2,6,11} ={9,19,13,5,12,8,7,4,21,2,6,11} ={9,5,13,19,12,8,7,4,21,2,6,11} ={9,5 ...; 个人分类: 数据结构与算法|2226 次阅读|0 个评论

分享算法导论第六章堆排序思考题: 2014-1-7 15:34; 6.1 (用插入的方法建堆)我们可以通过反复调用MAX-HEAP-INSERT实现向一个堆中插入元素，考虑BUILD-MAX-HEAP的如下实现方式： BULID-MAX-HEAP(A) A.heap-size=1 for i=2 to A.length MAX-HEAP-INSERT(A,A ) a.当输入数据相同的时候，BULID-MAX-HEAP和BULID-MAX-HEAP’生成的堆是否总是一样？瑞国是，请证明；否 ...; 个人分类: 数据结构与算法|828 次阅读|0 个评论

分享算法导论第六章6.5优先队列课后答案。: 2014-1-5 19:48; 6.5-1 试说明HEAP-EXTRACT-MAX在堆A={15,13,9,5,12,8,7,4,0,6,2,1}上的操作过程。 view plain copy spanstyle= "font-size:14px;" HEAP-EXTRACT-MAX(A) if (A.heap-size1) //堆中元素是否为空 ...; 个人分类: 数据结构与算法|2759 次阅读|0 个评论

12 3 / 3 页下一页

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-23 23:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部