计算机问题求解一论题2-4 -组合与计数 2016年03月17日
计算机问题求解 – 论题2-4 - 组合与计数 2016年03月17日
问题1： 计数在算法分析中为什么很重要？
(1) for i 1 to n-1 (2】 for j i+1 to n (3】 iE(A[i]>A[j]】 (4) exchange A[i]and A[j] How many times is the comparison A[i]A[j]made in Line 3? critical operation Principle 1.1 (Sum Principle) The size of a union of a family of mutually disjoint finite sets is the sum of the sizes of the sets. =∑1S
critical operation
问题2： 你如何理解这里所体现 的“抽象”过程？ 我们究竟要数什么？
我们究竟要数什么？
操作计数与子集计数 相同的情况，不同的抽象： 在排序的例子里，对任意含两个元素的子 集，我们需要做一次比较 则比较次数等于个元素的集合所有的两 个元素的子集的个数。 n(n-1) 2
操作计数 与 子集计数 相同的情况，不同的抽象： 在排序的例子里，对任意含两个元素的子 集，我们需要做一次比较 则比较次数等于n个元素的集合所有的两 个元素的子集的个数