《算法导论》第三章 练习题 Exercise
3.1-1 假设存在 h(n) = Θ(f(n)+g(n)) ，由渐进符号 Θ 的性质知存在三个正常量c1、 c2、n0，当n ≥ n0时，使得 c1·(f(n)+g(n)) ≤ h(n) ≤ c2·(f(n)+g(n))，当 h(n) = max(f(n), h(n)) 时，令 c1 = 0....
算法导论第三章习题答案（第三版） Introduction to Algorithm
Exercises 3.1-1 因为f (n)与g(n)是渐近非负的，所以存在 ， 使得 f(n),g(n)>0，可以看出存在 ， 使得 ， 所以可以证出max{f(n),g(n)}=Θ(f(n)+g(n))。 3.1-2 根据题意可知， 当 时成立，...
《算法导论》系列课后练习题之-第三章《函数的增长》(下)
3.2-1 证明：若f(n)和g(n)是单调递增的函数，则f(n)+g(n)和f(g(n))也是单调递增的；另外，若f(n)和g(n)是非负的，那么f(n)*g(n)是单调递增的。 证：若n1>n2,则有f(n1)+g(n1) - f(n2) - g(n2) = (f(n1)...
算法导论 练习题 3.2-3
由于n>=1时，2的n次方永远大于n! n>1时，n!永远小于n的n次方 所以后面两个小问题得证。...
算法导论2.3-7习题解答(合并排序算法及二分查找)
CLRS 2.3-7 ：请给出一个运行时间为O(nlgn)的算法，是之能在一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。 算法思想：1.先运用合并排序进行排序 O(nlgn)，2.然后运用二分查找法寻找y，y = x - a[i]； 代码如下： 1 #i...
算法导论 3.2-5
问题 哪一个在渐近上更大些： 还是 ？ 分析 通过计算得 根据n的log星定义 可以看出 = + 1 所以 是 的对数函数，而 是 的多项式函数 因为任何多项是函数增长的都比对数函数快，所以 增长的快些。...
算法导论2.3-7
方法1、 先排序，然后比较： 1 int i=0, j=n-1; 2 int b=0; 3 while (i<j) 4 { 5 int k=s[i]+s[j]; 6 if (k==x) b=1,break; 7 else if (k<x) i...
算法导论9.3-6
题目： 对一个含有n个元素的集合来说，所谓k分位数（the kth quantile），就是能把已排序的集合分成k个大小相等的集合的k-1个顺序统计量。给出一个能列出某一集合的k分位数的O(nlgk)时间的算法 思路： 每个子集合的元素个数为t = n / k，A[j]是数组A中下标为j的元素，A(...
算法导论-第13章-红黑树
一、概念 1.定义与性质 （1）定义 红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK。 且满足 (a)每个结点或是红的，或是黑的 (b)根结点是黑的 (c)每个叶结点（NIL）是黑的 (d)如果一个结点是红...
算法导论第十章基本数据结构
10.1栈与队列 （1） 栈 概念定义：栈属于动态集合，采用先进后出策略（LIFO）。基本操作是压入（PUSH）和弹出（POP）。如果s.top=0，表示栈空，如果试图对空栈进行POP操作会发生下溢（underflow）。如果s.top>n,表示栈满，如果进行PUSH操作会发生上溢（overf...
算法导论 9.3-6 nlgk时间求k分位数
一、题目 对一个含有n个元素的集合来说，所谓k分位数（the kth quantile），就是能把已排序的集合分成k个大小相等的集合的k-1个顺序统计量。给出一个能列出某一集合的k分位数的O(nlgk)时间的算法 二、思考 令每个子集合的元素个数为t = n / k，A[j]是数组A中下标为j的元...
算法导论 第四部分——基本数据结构——第15章：动态规划
前言：动态规划的概念 动态规划（dynamic programming）是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分为一些独立的子问题，递归的求解各个问题，然后合并子问题的解而得到原问题的解。例如归并排序，快速排序都是采用分治算法思想。本书在第二章介绍归并排序时，详细介绍了分治算法的...
算法导论2.1-4
题目 有两个各存放在数组A和B中的n位二进制整数，考虑他们的相加问题。（翻译的够烂）两个整数的和存放在有n+1个元素的数组C中，请给出这个问题的形式化描述，并给出伪代码。 分析 考虑两个1位二进制数a和b，假设它们的和c是个2位二进制数，c[1]=a b，c[2]=(a+b)/2=...
算法导论之2.3-7练习题
题目：给出一个Θ(nlgn)时间的算法。判断在集合S中，是否存在两个元素的和为x。 算法导论的教师手册解法如下：1.对集合S排序。 2.创建集合T = {z : z = x − y ，y ∈ S}。 3.对集合T排序。 4.去除S和T中的重复元素。 5.按照从小到大顺序或者从大到小顺...
算法导论9.1-1习题解答(二叉树)
CLRS 9.1-1 : 证明：在最坏情况下，利用n + [lgn] - 2此比较，即可找到n个元素中的第2小元素。（提示：同时找最小元素) 算法思想： 1.将数组中的元素分组，每组两个元素，然后比较每组中的两个元素得到最小值，重新得到包含原来一半元素的数组，继续重复上述过程，那么最后一个元素必然为...
从头看算法导论 习题2.3-7 深入分析
题目：请给出一个时间复杂度为nlogn的算法，使之能够在给定一个由n个整数的构成的整合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。 算法思想：1.先运用合并排序进行排序 O(nlgn)，2.然后运用二分查找法寻找y，y = x - a[i]，算法的时间复杂度小于nlogn,所以总的...
算法导论2.3-7习题
先使用归并排序进行排序，再建立其补集，对这两个排序后的集合进行元素比较，找到相同元素即寻找到答案 def findthecomplementary(s, x): l1 = list(s) l2 = [] n = len(l1) mergesort(l1, 0, n-1) ...
算法导论 Exercises 9.3-6
Problem Description: The kth quantiles of an n-element set are the k - 1 order statistics that divide the sorted set intok equal-sized sets (to within...
算法导论 2.1-4
题目 有两个各存放在数组A和B中的n位二进制整数，考虑他们的相加问题。（翻译的够烂）两个整数的和存放在有n+1个元素的数组C中，请给出这个问题的形式化描述，并给出伪代码。 分析 考虑两个1位二进制数a和b，假设它们的和c是个2位二进制数，c[1]=a b，c[2]=(a+b)/2=...
算法导论 习题2.1-4
有两个各存放在数组A和B中的n位二进制整数，考虑它们的相加问题。两个整数的和以二进制形式存放在具有(n+1)个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。 以下是我写的C++代码，如有错误请指出 #include "stdafx.h"#include<iostream>#i...