算法导论 10.3-4 紧凑的多重数组
一、题目： 我们常常希望一个双链表中的所有元素在存储器中能够紧凑地排列在一起，例如使用多重数组表示中的前m个下标位置（在一个分页的虚拟计算机环境中情况就是这样的）。假设链表以外没有指向链表元素的指针，请说明如何实现过程ALLOCATE_OBJECT和FREE_OBJECT，才能使这种表比较紧凑。（提...
算法导论：快速找出无序数组中第k小的数
题目描述： 给定一个无序整数数组，返回这个数组中第k小的数。 解析： 最平常的思路是将数组排序，最快的排序是快排，然后返回已排序数组的第k个数，算法时间复杂度为O（nlogn），空间复杂度为O（1）。使用快排的思想，但是每次只对patition之后的数组的一半递归，这样可以将时间复杂度将为O（n）。...
MIT算法导论——第七讲.哈希表
从作用上来讲，构建哈希表的目的是把搜索的时间复杂度降低到O（1），考虑到一个长度为n的序列，如果依次去比较进行搜索的话，时间复杂度是θ（n），或者对其先进行排序然后再搜索会更快一些，但这两种方法都不是最快的方法。第一个话题： 计算机里面所有存储的内容都是数字，因此我们研究对数字构建哈希表就够了。先...
算法导论分而治之学习笔记
The divide-and-conquer design paradigm 1. Divide the problem (instance) into subproblems. 2. Conquer the subproblems by solving them recursively. ...
C语言 插入排序 算法导论chapter2
1 #include <stdio.h> 2 #define N 10 3 //INSERTION-SORT 4 int main() 5 { 6 int i,j,a[N]={5,1,2,3,6,0,4,7,9,8}; 7 int key; 8 for(j=...
请教：算法导论（第二版）的两道题
page193 9.3-7 Let X[1..n] and Y[1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lgn)-time algorithm to find th...
Felomeng算法导论（第二版）学习笔记Chapter2（使用C#实现）
第二章 Getting Started 插入排序（Insertion Sort）C#实现: int i,j,key; for( j = 1; j < numbers.Length; j ++) { ...
B树——算法导论(25)
1. 简介在之前我们学习了红黑树，今天再学习一种树——B树。它与红黑树有许多类似的地方，比如都是平衡搜索树， 但它们在功能和结构上却有较大的差别。从功能上看，B树是为磁盘或其他存储设备设计的，能够有效的降低磁盘的I/O操作数，因此我们经常看到有许多数据库系统使用B树或B树的变种作为储存的数据结构；从...
基于visual Studio2013解决算法导论之008快速排序算法
题目快速排序解决代码及点评#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <time.h>void PrintArr(int *pnArr, int nLen){f...
请问各位高手是在什么阶段看的算法导论？
我的目标是能像你们一样用严谨的数学知识来分析算法，制定算法。就是希望将数学思维贯通于算法之中。 知道在坛子里有许多的大牛，想冒昧的问下你们都是在数学知识，数据结构算法知识掌握到什么情况下才去看的算法导论。 以及看完导论之后最大收获，尽量讲详细点哈。 还有导论对于现在的你们来说是不是已经算比较简...
算法导论-用于不想交集合的数据结构（并查集）-kruskal最小生成树算法
并查集学习： 并查集：(union-find sets) 一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数等。最完美的应用当属：实现Kruskar算法求最小生成树。 并查集的精髓（即它的三种操作，结合实现代码模板进...
【算法导论】决策树下界的形象理解？
我在看算法导论的比较排序，作者用决策树证明了比较排序的下界是nlgn 但是证明过程是用比较法， 能否用更加形象的方式解释这个nlgn是怎么来的呢？ （比如我尝试这样解释：对于n个数的排序，每个数至少需要比较lgn次，那么这个lgn又是怎么来的呢？） 决策树排序的下界 如果决策树是针对n个元素排序，...
算法导论第十八章 B树
本文首发于我的公众号 Linux云计算网络（id: cloud_dev） ，专注于干货分享，号内有 10T 书籍和视频资源，后台回复 「1024」 即可领取，欢迎大家关注，二维码文末可以扫。一、高级数据结构本章以后到第21章（并查集）隶属于高级数据结构的内容。前面还留了两章：贪心算法和摊还分析，打算...
【原创】《算法导论》链表一章带星习题试解——附C语言实现
原题：双向链表中，需要三个基本数据，一个携带具体数据，一个携带指向上一环节的prev指针，一个携带指向下一环节的next指针。请改写双向链表，仅用一个指针np实现双向链表的功能。定义np为next XOR prev，请根据表头提供的信息，为双向链表编写插入函数、删除函数和查找函数，并在O(1)时间内...
【算法导论 in lambda】用lambda来重写插入排序算法
插入排序原本的实现方式之一： public int[] sort_ori(int[] ins) { for (int i = 1; i < ins.length; i++) { int currentIndex = i; int ...
《算法导论》排序算法
看《算法导论》写的部分代码，做个记录。 #include <iostream>#include <cmath>#include <vector>#define maxNumber 100000000;/*-----------------------------...
算法导论学习---红黑树具体解释之插入(C语言实现)
前面我们学习二叉搜索树的时候发如今一些情况下其高度不是非常均匀，甚至有时候会退化成一条长链,所以我们引用一些”平衡”的二叉搜索树。红黑树就是一种”平衡”的二叉搜索树，它通过在每一个结点附加颜色位和路径上的一些约束条件能够保证在最坏的情况下基本动态集合操作的时间复杂度为O(nlgn).以下会总结红黑树...
"《算法导论》之‘排序’"：线性时间排序
本文参考自一博文与《算法导论》。《算法导论》之前介绍了合并排序、堆排序和快速排序的特点及运行时间。合并排序和堆排序在最坏情况下达到O(nlgn)，而快速排序最坏情况下达到O(n^2)，平均情况下达到O(nlgn)，因此合并排序和堆排序是渐进最优的。这些排序在执行过程中各元素的次序基于输入元素间的比较...
计算机科学导论---算法
算法：它是一组明确步骤的有序集合，它能产生结果，并在有限的时间内终止。 计算机科学中，最普遍的应用是排序，即根据数据的值对它们进行顺序排列。 这里介绍三种最基础的排序算法：选择、冒泡、插入。它们也是其他排序算法的基础。数据列表可看成两个子列表（已排序和未排序），它们通过假想的墙分开。 选择排序：每一...
《算法导论（第3版）》读书笔记（一）算法基础
本篇内容主要涉及《算法导论》一书中的第二章知识，涉及的内容有插入排序和归并排序插入排序对于插入排序有个很明显的显示生活例子来帮助我们理解，插入排序的工作原理就像打扑克牌一样，右手从桌面上拿起一张牌，然后再左手那一堆已经按牌面大小排好序的牌找到这张牌应该在的位置，然后插入进去。通俗点讲，就是从未排序的...