当前位置：文档之家 › 计算机算法分析-第四章

计算机算法分析-第四章

  • 格式：pdf
  • 大小：184.99 KB
  • 文档页数：26

最好， 平均， Θ(1), Θ(log n), 最好， Θ(log n),
最坏 Θ(log n) 最坏 Θ(log n)

失败:

平均， Θ(log n),
P99-6
对于含n个节点的二元树，证明
E(n) = I(n) + 2n 其中，E(n)、I(n)分别为外部和内部 路径的长度
归纳法进行证明： n = 1时，结论显然成立 假设n = k时结论成立 当n = k + 1时，将深度为d的叶子内节点替换 为外节点后能得到含k个内节点的比较树
P99-2
递推表达式
设n=2k则: T(n)=T(2k)=2T(2k-1)+f(2k) =2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) # =2kT(1)+2k-1f(2)+2k-2f(22)+…+20f(2k)
=2kg(n)+ 2k-1f(2)+2k-2f(22)+…+20f(2k)
计算机算法分析—习题课
2014年4月 第四章：2 、3、 5、 6、10、11、23
P99-2
在下列情况下求解 4.1 节的递归关系式
n足够小 ⎧ g ( n) T(n)= ⎨ 否则 ⎩2T (n / 2) ＋ f (n)
当①g(n)=O(1)和 f(n)=O(n)； ②g(n)=O(1)和 f(n)=O(1)。
g(n)=O(1)和f(n)=O(1)
当g(n)=O(1)和f(n)=O(1)时， 不妨设g(n) ≤ c，f(n) ≤ d，则： T(n) = T(2k) ≤ c2k+2k-1d+2k-2d+…+20d = c2k+d(2k － 1) = (c+d)n － d = O(n)
P99-3

根据4.2节开始所给出的二分检索策略，写一 个二分检索的递归过程。
两个序列交错大小 需要比较n-1次 一个序列完全大于/小于另一个序列 比较n/2次

最好情况


差异都是线性的，不改变复杂性的阶

最好情况也是Θ(nlogn), 平均复杂度Θ(nlogn)
P99-11

写一个“由底向上”的归并分类算法，从而取消 对栈空间的利用。

见《数据结构》--- 合并排序
P=(A11+A22)(B11+B22) Q=(A21+A22)B11 R=A11(B12-B22) S=A22(B21-B11)
T=(A11+A12)B22 U=(A21-A11)(B11+B12) V=(A12-A22)(B21+B22)
C22=P+R-Q+U =(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21A11)(B11+B12) = A11B11+A22B11+A11B22+A22B22+ A11B12-A11B22A21B11-A22B11 +A21B11 +A21B12-A11B11-A11B12 =A22B22+A21B12
procedure MPass(R, n, len, X) integer n, len, i; i←1; while i ≤ n – 2 * len + 1 do Merge(R, i, i＋len – 1, i＋2*len–1, X); i←i＋2*len; repeat if i+len–1 < n then Merge(R, i, i+len–1, n, X） else for j = i to n do X(j) ← R(j) end MPass
P=(A11+A22)(B11+B22) Q=(A21+A22)B11 R=A11(B12-B22) S=A22(B21-B11)
T=(A11+A12)B22 U=(A21-A11)(B11+B12) V=(A12-A22)(B21+B22)
C12=R+T = A11B12-A11B22 +A11B22+A12B22 = A11B12 +A12B22 C21=Q+S = A21B11+A22B11 +A22B21-A22B11 = A21B11 +A22B21
C11=P+S-T+V =(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22) =A11B11+A22B11+A11B22+A22B22 +A22B21-A22B11 A11B22-A12B22 +A12B21+ A12B22-A22B21-A22B22 =A11B11 +A12B21
P99-10
过程MERGESORT的最坏情况时 间是O(nlogn)，它的最好情况时间 是什么？能说归并分类的时间是 Θ(nlogn)吗？

最好情况：

对有序文件进行排序 归并的次数不会发生变化----log(n)次 归并中比较的次数会发生变化（两个长n/2序列归 并）


分析

最坏情况

P99-5
作一个“三分”检索算法，它首先检
查n/3处的元素是否等于某个x的 值，然后检查2n/3处的元素。这 样，或者找到x，或者把集合缩小 到原来的1/3。分析此算法在各种 情况下的计算复杂度。
procedure ThriSearch(A, x, n, j) integer low, high, p1, p2 low←1; high←n while low≤high do p1← ⎣(2low+high+1)/3 ⎦ p2← ⎣ (low+2high+2)/3 ⎦ case :x=A(p1): j←p1; return :x=A(p2): j←p2; return :x<A(p1): high←p1-1 :x>A(p2): low ←p2+1 :else: low←p1+1; high←p2-1
I(n) = I(k) + d E(n) = E(k) – d + 2d + 2 = I(k) + 2k + d + 2 = I(n) + 2k + 2 = I(n) + 2n
另一种证明思路： 假设左右子树分别含n1、n2个节点，显然 n1 + n2 = n − 1 E(n1) = I(n1) + 2n1、E(n2) = I(n2) + 2n2 E(n) = E(n1) + E(n2) + n +1 = I(n1) + 2n1+ I(n2) + 2n2 + n +1 = [ I(n1) + I(n2) + n1 + n2] + [n1 + n2 + 1 + n] = I(n) + 2n
P99-23
通过手算证明（4.9）和(4.10)式确
实能得到C11,C12,C21和C22的正确值。
P=(A11+A22)(B11+B22) Q=(A21+A22)B11 R=A11(B12-B22) S=A22(B21-B11)
T=(A11+A12)B22 U=(A21-A11)(B11+B12) V=(A12-A22)(B21+B22)
Procedure BINSRCH1(A, low, high, x, j) integer mid, low, high, j; if low≤high then mid← ⎣(low+high)/2 ⎦; case :x=A(mid): j←mid; :x < A(mid): BINSRCH1(A, low, mid-1, x, j); :else: BINSRCH1(A, mid+1, high, x, j); endcase else j←0; endif end BINSRCH1
P99-2
g(n)=O(1)和f(n)=O(n)
当g(n)=O(1)和f(n)=O(n)时 不妨设g(n) ≤ a，f(n) ≤ bn，则： T(n)=T(2k) ≤ 2ka+ 2k-1×2b+2k-2×22b+…+20×2kb = 2ka+kb2k = an+bnlog2n=O(nlogn)
P99-2
Procedure MSort(R, n) // 直接两路合并排序 算法，X是辅助文件，其记录结构与R相同 integer len, n; len ← 1; while len < n do MPass(R, n, len, X); len ← 2 * len; MPass(X, n, len, R); len ←2 * len; repeat end MSort
endcase repeat j←0 end ThriSearch
实例运行 在数组 { -15, -6, 0, 7, 9, 23, 54, 82, 101 }中找 9和53
1
2
3 0
4 7
5 9
6 23
7 54
8 82
9 101
-15 -6
查9和53
时间复杂度



算法每一步的时间为常数，复杂度取决于循环 次数，也即路径长度或路径长度加1 E(n) = I(n)+ ⎡3n/2⎤ 成功:

合集下载

第四章电力系统潮流的计算机算法

第四章电力系统潮流的计算机算法


1 z ij
(4) 原有节点ij之间阻抗由Zij变为Zij’
i j
－Zij
Yii
Yj
j
y i' jyi
j
1 z'ij
1 zij
Z’ij
Yij＝Yji
yi
j
y
i'
j＝z1ij
1 z'ij
(4) 原有节点ij之间变压器的变比由K*变为K*’时。
i j
返回
-ZT K*:1
ZT K’*:1
Z1 Y T(k-1 )/k
(2)节点导纳矩阵是稀疏矩阵，非对角非零 元素的个数等于对应节点所连的不接地 支路数。
(3)对角元素（自导纳）等于相应节点所连 支路的导纳之和。
(4)非对角元素（互导纳）等于两节点间支 路导纳的负值。
(5)节点导纳矩阵是对称方阵，只需求上三 角或是下三角元素。
标准变比：在采用有名值时，是指归算参数时所 取的变比。采用标么值时，是指折算参数时所 取各基准电压之比。
•
I1
Z 1 U 1 k :1
I1
•
I2
ZT
U2
Z2
U 1/k
I2
～～
S1 ＝ S 2
U1I 1 U1I2 k
I1 I2 / k U 1/kU 2I 2ZT
I1
U1 ZT k 2
U2 ZT k
I2
U1 ZT k
U2 ZT
I 1(y10y12)U 1y12 U 2 I 2 y2U 1 1(y20y21)U 2
2n个扰动变量是已知的，给定2（n－1）个控制变量， 给定2个状态变量，要求确定2（n－1）个状态变量。 已知：4n个变量，待求：2n个变量
高一《数据与计算》(必修)第四章《算法及其特征》

高一《数据与计算》(必修)第四章《算法及其特征》

高一《数据与计算》（必修）第四章《算法及其特征》一、引言在计算机科学领域，算法是指用来解决问题的一系列步骤或方法。

在本章中，我们将学习什么是算法，算法的特征，以及算法设计的基本原则。

二、算法的概念2.1 算法定义算法是对问题求解步骤的一种描述，是指令的有限序列。

算法是基于确定性的、可执行的，并能在有限步骤内完成的。

一个好的算法应具备清晰、无二义性、可行性和有穷性。

2.2 算法的基本特征•输入：算法具有零个或多个输入。

输入是算法从外部获取的数据，用于算法的运行。

•输出：算法具有一个或多个输出。

输出是算法根据输入产生的结果。

•有穷性：算法应该在有限次的执行后终止。

•确定性：算法的每一步都应该明确且无二义性地定义。

•可行性：算法中的每一步都应该是可行的，即能够被计算机执行。

三、算法设计的基本原则在设计算法时，我们需要遵循以下基本原则：3.1 合理性算法应该能够实现给定的问题解决要求。

它需要合理地应对问题的各种情况和输入。

3.2 可读性算法的设计应该易于理解和阅读。

良好的代码注释和适当的命名方式，可以提高算法的可读性。

3.3 健壮性算法应该能够正确地处理各种异常情况，例如无效输入或异常数据。

算法的设计应尽量减少计算的时间。

一个高效的算法应该能够在合理的时间内给出结果。

3.5 空间效率算法的设计应尽量减少需要的存储空间。

一个高效的算法应该能够有效地使用计算机的内存。

四、常见算法在计算机科学中，有许多已经被广泛使用的算法。

下面是一些常见的算法：4.1 排序算法•冒泡排序•插入排序•选择排序•快速排序•归并排序4.2 查找算法•顺序查找•二分查找•哈希查找4.3 图算法•最短路径算法•拓扑排序算法•最小生成树算法4.4 字符串匹配算法•BF算法•KMP算法五、算法的复杂度分析在算法设计中，我们需要对算法的复杂度进行评估。

算法的复杂度分析可以通过对其时间复杂度和空间复杂度进行评估。

时间复杂度描述了算法在运行时所需要的时间。

(整理)《计算机算法-设计与分析导论》课后习题答案.

(整理)《计算机算法-设计与分析导论》课后习题答案.

4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort 的算法。

它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max ，然后将该元素同未排序序列中的最后一个元素交换。

这时，max 元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max 已经不在未排序序列之中了。

重复上述过程直到完成整个序列的排序。

(a) 写出Maxsort 算法。

其中待排序序列为E ，含有n 个元素，脚标为范围为0,,1n -。

void Maxsort(Element[] E) { int maxID = 0;for (int i=E.length; i>1; i--) { for (int j=0; j<i; j++) {if (E[j] > E[maxID]) maxID = k; }E[i] <--> E[maxID]; } }最坏情况同平均情况是相同的都是11(1)()2n i n n C n i -=-==∑。

几遍浏览序列实现。

排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。

也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位起泡排序的最坏情况为逆序输入，比较次数为11(1)()2n i n n C n i -=-==∑。

(b) 最好情况为已排序，需要(n-1)次比较。

4.3： (a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k 时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k 个元素进行比较，当k元素大于k-1元素时，它为k个元素中最大的，命题成立；当k元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。

算法设计与分析第三版第四章课后习题答案

算法设计与分析第三版第四章课后习题答案

算法设计与分析第三版第四章课后习题答案4.1 线性时间选择问题习题4.1问题描述：给定一个长度为n的无序数组A和一个整数k，设计一个算法，找出数组A中第k小的元素。

算法思路：本题可以使用快速选择算法来解决。

快速选择算法是基于快速排序算法的思想，通过递归地划分数组来找到第k小的元素。

具体步骤如下： 1. 选择数组A的一个随机元素x作为枢纽元。

2. 使用x将数组划分为两个子数组A1和A2，其中A1中的元素小于等于x，A2中的元素大于x。

3. 如果k等于A1的长度，那么x就是第k小的元素，返回x。

4. 如果k小于A1的长度，那么第k小的元素在A1中，递归地在A1中寻找第k小的元素。

5. 如果k大于A1的长度，那么第k小的元素在A2中，递归地在A2中寻找第k-A1的长度小的元素。

6. 递归地重复上述步骤，直到找到第k小的元素。

算法实现：public class LinearTimeSelection {public static int select(int[] A, int k) { return selectHelper(A, 0, A.length - 1, k);}private static int selectHelper(int[] A, int left, int right, int k) {if (left == right) {return A[left];}int pivotIndex = partition(A, left, righ t);int length = pivotIndex - left + 1;if (k == length) {return A[pivotIndex];} else if (k < length) {return selectHelper(A, left, pivotInd ex - 1, k);} else {return selectHelper(A, pivotIndex + 1, right, k - length);}}private static int partition(int[] A, int lef t, int right) {int pivotIndex = left + (right - left) / 2;int pivotValue = A[pivotIndex];int i = left;int j = right;while (i <= j) {while (A[i] < pivotValue) {i++;}while (A[j] > pivotValue) {j--;}if (i <= j) {swap(A, i, j);i++;j--;}}return i - 1;}private static void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}}算法分析：快速选择算法的平均复杂度为O(n)，最坏情况下的复杂度为O(n^2)。