离散数学（第8章）函数.ppt

常用函数—单调递增函数设A,≤，B,≤为偏序集，f：A→B，如果对任意的x1,x2∈A，x1＜x2，就有f(x1)≤f(x2)，则称f为单调递增的； 如果对任意的x1,x2∈A,x1＜x2,就有f(x1)＜f(x2),则称f为严格单调递增的。类似的也可以定义单调递减和严格单调递减的函数。举例：f:R→R,f(x)＝x+1是严格单调递增的。 偏序集P({a,b}),R?，{0,1},≤，R?为包含关系，≤为一般的小于等于关系。令f：P({a,b})→{0,1}，f(?)＝f({a})＝f({b})＝0，f({a,b})=1， f是单调递增的,但不是严格单调递增的。常用函数—特征函数设A为集合，对于任意的A??A，A?的特征函数?A?:A→{0,1}定义为1，a∈A?0，a∈A?A??A?(a)＝举例:A的每一个子集A?都对应于一个特征函数，不同的子集对应于不同的特征函数。 例如A＝{a,b,c},则有 ??＝{a,0,b,0,c,0}， ?{a}＝{a,1,b,0,c,0} ?{a,b}＝{a,1,b,1,c,0}常用函数—自然映射设R是A上的等价关系，令g：A→A/R

g(a)=[a]，?a∈A称g是从A到商集A/R的自然映射。给定集合A和A上的等价关系R，就可以确定一个自然映射g：A→A/R。例如A＝{1,2,3}，R＝{1,2,2,1}∪IAg(1)＝g(2)＝{1,2},g(3)＝{3}不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射，而其他的自然映射一般来说只是满射。定义在自然数集合上的计数函数对于给定规模为n的输入，计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。排序和检索问题的基本运算是比较。矩阵乘法的基本运算是元素的相乘。估计算法在最坏情况下所做基本运算的次数记为W(n)。估计算法在平均情况下所做基本运算的次数记为A(n)。设f是定义在自然数集合上的函数，当n变得很大时，函数值f(n)的增长取决于函数的阶。阶越高的函数，算法的复杂度就越高，同时意味着算法的效率越低。算法分析的主要工作就是估计复杂度函数的阶。阶可以是： n，n2，n3，nlogn，logn，2n……定义在自然数集合上的计数函数若存在正数c和n0，使得对一切n≥n0，有0≤f(n)≤cg(n)，记作f(n)＝O(g(n))。若存在正数c和n0，使得对一切n≥n0，有0≤cg(n)≤f(n)，记作f(n)＝Ω(g(n))。若f(n)＝O(g(n))且f(n)＝Ω(g(n))，则f(n)＝Θ(g(n))。例如f(n)＝1/2n2-3n，则f(n)＝Θ(n2)g(n)＝6n3，则g(n)＝Θ(n3)8.2函数的复合与反函数函数的复合就是关系的右复合，一切和关系右复合有关的定理都适用于函数的复合。本节重点考虑在复合中特有的性质。定理8.1(复合函数基本定理)定理8.1设F,G是函数，则F?G也是函数，且满足（1）dom(F?G)＝{x|x∈domF∧F(x)∈domG}（2）?x∈dom(F?G)，有F?G(x)＝G(F(x))证明： 先证明F?G是函数。 因为F、G是关系，所以F?G也是关系。 若对某个x∈dom(F?G)，若有xF?Gy1和xF?Gy2，则 x,y1∈F?G∧x,y2∈F?G ? ?t1(x,t1∈F∧t1,y1∈G)∧?t2(x,t2∈F∧t2,y2∈G) ? ?t1?t2(t1＝t2∧t1,y1∈G∧t2,y2∈G) （F为函数） ? y1＝y2 （G为函数） 所以F?G为函数。定理8.1的证明定理8.1的证明任取x，(要证明dom(F?G)＝{x|x∈domF∧F(x)∈domG})x∈dom(F?G)??t?y(x,t∈F∧t,y∈G)??t(x∈domF∧t＝F(x)∧t∈domG)?x∈{x|x∈domF∧F(x)∈domG} 所以（1）得证。任取x，（要证明?x∈dom(F?G)，有F?G(x)＝G(F(x))）x∈domF∧F(x)∈domG?x,F(x)∈F∧F(x),G(F(x))∈G?x,G(F(x))∈F?G?x∈dom(F?G)∧F?G(x)＝G(F(x))