导论专题
摸鱼大数据——大数据导论
大数据导论 1、概念 大数据时代: 万物皆数据数据概念: 人类的行为及产生的事件的一种记录称之为数据数据价值: 对数据的内容进行深入分析，可以更好的帮助了解事和物在现实世界的运行规律 2、大数据诞生 大数据的诞生: 跟随着互联网的发展的,当全球互联网逐步建成（2000年左右），各大企业或政府单位拥有了海量的数据亟待处理。基于这个前提逐步诞生了以分布式的形式（即多台服务
《算法导论》学习笔记Chapter11散列表
散列表最重要的是散列函数的选择，一个好的散列函数应满足简单均匀散列假设特点：每个关键字都被等可能的散列到m个槽位中的任何一个，并与其它关键字已散列到哪个槽位无关。 遗憾的是上述条件很难检测到是否满足，因为很少能知道关键字散列所满足的概率分布，且各关键字可能并不是完全独立的。 实际中，可应用启发式方法构造性能好的散列函数。设计过程中，充分利用关键字分布的有用信息。 “除法散列”是一种较好的方法
《算法导论》学习笔记之Chapter10---数据结构之链表
链表定义：链表是这样一种数据结构，其中的各对象按线性顺序排列，与数组的线性顺序由下标决定不同，链表的顺序是由各个对象里的指针决定。 链表分为：单向链表，双向链表，还有循环链表。 链表支持的操作有：查找Search；插入Insert；删除Delete； 双向链表的查找操作就是从表头开始对比查找，很简单；插入操作，是根据插入的数据的指针属性来寻找要插入的位置；之后修改相关元素的pre和next指
《算法导论》学习笔记之Chapter10---队列的数组实现
紧接上一篇文章，本文记录数组实现队列的实现 队列的定义：顺序存储结构存储的队列称为顺序队列，是一个内部存储元素按顺序排列的列表，遵循先进先出原则。 需要理解的是队列的两个定义：队头front和队尾rear。两者都是指向队列元素的指针，队头指针始终指向队列最先进去的元素的前一个下标位置，初始值可设为-1。队尾指向队列最后进去的元素下标，初始值常为0。 判断队列是否为空的条件是：队头指针
《算法导论》学习笔记之Chapter9中位数和顺序统计量
第9章 中位数和顺序统计量 先定义：在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。一个中位数是它所属集合的“中点元素”。当n是奇数时，中位数是唯一的，位于i=n/2处。当n为偶数时，中位数有两个，分别位于i = n/2和i=n/2+1处。不考虑n的奇偶性，中位数总是出现在i=(n+1)/2向下取整处，也叫下中位数，和i=(n+2)/2向上取整处，也叫上中位数。本书默认下中
《算法导论》学习笔记之Chapter8线性时间排序
第8章 线性时间排序 前面介绍的包括归并排序，堆排序和快速排序，最后的次序都依赖于元素之间的比较，叫做比较排序。 归并排序和堆排序都是渐近最优的，且任何已知的比较排序最多就是在常数因子上优于他们。即比较排序的时间复杂度下界就是Ω(nlogn)。 线性时间排序算法，包括：基数排序，计数排序和桶排序，是靠运算不是比较来排序的，下界Ω(nlogn)不是他们的下界。 计数排序：假设n个输入元
《算法导论》学习之关于如何利用排序算法，从1亿个数中，选出最大（小）的100个数
首先声明：本文内容是参考别人的博客，链接为：http://blog.csdn.net/beiyeqingteng/article/details/7534489 前言： 刚刚在CSDN上看到一个网友利用最小堆实现 “ 获取一亿数据获取前100个最大值” 。原帖请看：http://blog.csdn.net/yjflinchong/article/details/7533972。 然后自
《算法导论》学习笔记之Chapter7快速排序
第七章 快速排序 对于包含n个数的数组来说，快速排序是一种最坏情况时间复杂度为θ(n.^2)的排序算法。虽然最坏情况时间复杂度很很差，但快速排序通常是实际排序应用中最好的选择，因为他的平均性能非常好：它的期望时间复杂度为θ(nlogn)，而且θ(nlogn)中隐含的常数因子非常小。同时，快速排序还能够进行原址排序，甚至在虚存环境中也能很好的工作。 其中基于随机抽样的快排算法，期望时间复杂
《算法导论》Chapter6 堆
先介绍 堆的几个基本性质： MAX-HEAPIFY过程，时间复杂度为O(lgn)。他是维护最大堆性质的关键； BUILD-MAX-HEAP过程，具有线性时间复杂度，功能是从无序的输入数据数组中构造一个最大堆； HEAPSORT过程，时间复杂度为O(nlgn)，其功能是对一个数组进行原址排序； MAX-HEAP-INSERT,HEAP-EXTRACT-MAX,HEAP-I
《算法导论》学习笔记之Chapter5.1
5.1-2 问题：请描述RANDOM(a, b)过程的一种实现，它只调用RANDOM(0, 1)。作为a和b的函数，你的过程的期望运行时间是多少？ 伪代码： [plai n] view plain copy RANDOM(a, b) 1 n = b - a + 1 2 generate a new array A[1..<lgn>] //<lgn
《算法导论》学习笔记之Chapter4.2矩阵乘法Strassen
4.2 矩阵乘法，代码如下： //求两个方阵的乘积public static int[][] squareMatrixMultiply(int[][] a, int[][] b){int n = a.length;int[][] c = new int[n][n];for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){c[i][j]
文心一言 VS 讯飞星火 VS chatgpt （259）-- 算法导论19.3 2题
二、使用聚合分析来证明 FIB-HEAP-DECREASE-KEY 的 O(1) 摊还时间是每一个操作的平均代价。如果要写代码，请用go语言。 文心一言： FIB-HEAP-DECREASE-KEY 是斐波那契堆（Fibonacci Heap）操作中的一个，它允许我们减少堆中某个节点的键值，并可能触发一系列操作来维护堆的性质。然而，直接证明 FIB-HEAP-DECREASE-KEY 的摊还时
文心一言 VS 讯飞星火 VS chatgpt （258）-- 算法导论19.3 1题
一、假定斐波那契堆中一个根 x 被标记了。解释 x 是如何成为一个被标记的根的。试说明 x 是否被标记对分析并没有影响，即使它不是一个先被链接到另一个结点，后又丢失了个孩子的根。如果要写代码，请用go语言。 文心一言： 斐波那契堆（Fibonacci Heap）是一种特殊的优先队列数据结构，它使用了一种叫做“合并树”的结构来组织节点。在斐波那契堆中，节点可以被标记（marked）或未标记（un
算法导论（八）——动态规划贪婪算法
算法导论（八）——动态规划&贪婪算法 【主要参考资料：MIT算法导论视频，《数据结构，算法与应用，c++语言描述》】 动态规划方法通常用来求解最优化问题，从可行解中寻找具有最优值的解，得到的是问题的一个最优解(an optimal solution)。 求解的问题需具备要素：最优子结构和子问题重叠。算法对每个子问题只求解
算法导论（七）——跳跃表自组织表，竞争性分析
算法导论（七）——跳跃表&自组织表，竞争性分析 1. 背景： ①为了提高有序链表的查找性能，考虑在部分或全部节点上增加额外的指针，以便查找时跳过若干点，不必从左到右连续查看。 方法： 1. 散列表（哈希表）：操作时间提至O(1)，但最坏是O(n) 【应用】文本压缩解压p.260 LZW压缩
算法导论（五）——树
算法导论（五）——树 【主要参考资料：MIT算法导论视频，《数据结构，算法与应用，c++语言描述》】 完全二叉树： 只有最下面两层度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。 已知节点总数为n，则叶子结点数n0＝（n＋1）/2 。 假设元素编号i[1,n]，若i==1,则为根元
算法导论（四）——哈希表平摊分析
算法导论（四）——哈希表&平摊分析 1. 背景: symbol-table problem(tableS holding n records)，执行操作插入，删除，搜素。 要使在列表中查找元素的效率达到Θ(1)【给定一个关键字Key（整数）,通过一个定义好的散列函数，可以计算出数据存放的索引位置，这样免去遍历】 若直接映射，则占
算法导论（三）——分治法
divide conquer combine分而治之： 例子： 求x的n次方: a^n传统的做法就是循环相乘n次，算法效率为Θ(n)。但是如果采用分治法的思想，算法效率可以提高到Θ(lgn) 二分查找；归并排序； 快速排序；http://www.cnblogs.com/zhoutaotao/p/3970099.html(快排，随机快排) 斐波那契数列http://www.cnbl
算法导论（二）——排序算法整理
算法导论（二）——排序算法整理 【主要参考资料：MIT算法导论视频，《数据结构，算法与应用，c++语言描述》】 排序算法： 1. 时间开销 •排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 •算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算 2. 空间开销 算法执行时所需的附
文心一言 VS 讯飞星火 VS chatgpt （257）-- 算法导论19.2 1题
一、给出图19-4(m)中的斐波那契堆调用 FIB-HEAP-EXTRACT-MIN 后得到的斐波那契堆。如果要写代码，请用go语言。 文心一言： 由于我不能直接画出图19-4(m)中的斐波那契堆，我将基于斐波那契堆的基本结构和操作FIB-HEAP-EXTRACT-MIN的一般行为来描述如何更新斐波那契堆。 在斐波那契堆中，每个节点都有一个度（指向它的孩子节点的数量）、一个标记（用于合并操作
算法导论 3.1-8
问题 可以将我们的表示法扩展到有两个参数n和m的情况，其中n和m的值可以以不同的速率，互相独立地趋近与无穷。对于给定的函数g(n,m),O(g(n,m))为函数集O(g(n,m))={f(n,m):存在正整数c, n0和m0，使对所有n>=n0及m>=m0,有0<=f(n,m)<=cg(n,m)}。 给出对应的 和 的定义。 分析 ={f(n,m):存在正整数c,n0和m0,使对所有n
算法导论 3.1-7
问题 证明 是空集。 分析 证明：用反证法 设f(n)=o(g(n)),h(n)=w(g(n)) 根据定义存在正常数n0，对任意正常数c，使得当n>=n0时，有0 <= f(n) <= cg(n) 并且存在正常数n1，对任意正常数c，使得当n>=n1时，有0 <= cg(n) <= h(n) 假设不是空集，则f(n)与h(n)存在交集i(n)，那么i(n)满足 cg(n) <= i(n) <
算法导论 3.1-6
问题 证明：一个算法的运行时间是 当且仅当其最坏情况运行时间是 ，且最佳情况运行时间是 分析 证明： 充分条件： 算法的运行时间为T(n) 由题意可知，存在c1,c2,n0,当n>=n0时，0 < c1g(n) <= T(n) <= c2g(n) 因为最坏运行时间Tmax(n) >= T(n) 存在c1，n0，当n>=n0时，0 < c1g(n) <= Tmax(n) 即最坏情况运行时
算法导论 3.1-5
问题 证明定理3.1 分析 证明： 充分条件：显然是成立的，略 必要条件： 由f(n)=O(g(n))得当n>=n1时，0<=f(n)<=c1g(n) 由f(n)= 得当n>=n2时，0<=c2g(n)<=f(n) 所以，当n>=max(n1,n2)时，0<=c2g(n)<=f(n)<=c1g(n),满足渐近确界定义，得证
算法导论 3.1-4
问题 成立吗？ 成立吗？ 分析 证明：因为当n>0时， 所以取c=2，n0=0满足渐近上界定义，所以成立 因为 令 显然a>=1,从而对于n > 0, 所以不成立