函数的阶 定义: 若存在正数c和皿使得对于一切n≥m,有0≤f(n)scg(n),则记作 f(n=O(g(n); 若存在正数c和叫使得对于一切n≥n有0≤cg(n)≤fn),则记作 f(n)=(g(n); 若f(n)=O(g(m)且f(n)=92(g(m),则记作f(n)=⊙(g(n); 例如 f(n)=n2,g(n)=m3,h(m)=n2+n,则有 f(n)=O(g(m),g(n)=9(f(n),f(n)=o(h(m) 些常用函数的阶的比较 n! 2, nlogn, logn, loglog, 衡量算法的复杂性 给定规模为n的输入,算法所做基本运算的次数可表示为n的函数f(n) 当n较大时,函数值f(m)的增长取决于函数的阶阶越高的函数增长的 越快相应的算法的复杂度就越高,同时意味着算法的效率越低 16
16 函数的阶 z 定义: ¾ 若存在正数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)); z 例如: ¾ f(n)=n2, g(n)=n3, h(n)=n2+n, 则有 f(n)=O(g(n)), g(n)=Ω(f(n)), f(n)=Θ(h(n)) z 一些常用函数的阶的比较 ¾ n!, 2n, nlogn, logn, loglogn, …… z 衡量算法的复杂性 ¾ 给定规模为n的输入,算法所做基本运算的次数可表示为n的函数f(n). ¾ 当n较大时, 函数值f(n)的增长取决于函数的阶. 阶越高的函数,增长的 越快,相应的算法的复杂度就越高,同时意味着算法的效率越低
函数的复合 函数是一种特殊的二元关系,函数的复合就是关系的右 复合.关系右复合有关的定理都可用于函数的复合
17 函数的复合 函数是一种特殊的二元关系, 函数的复合就是关系的右 复合.关系右复合有关的定理都可用于函数的复合
函数的复合 定理:设F和G是函数,则FG也是函数,且满足 (1)dom(FG)={x|x∈domF∧F(x)∈domG} 2)VxEdom(FoG), A: FoG(x)=G(F(x)) 证明:首先证明FG为函数 因为F和G是关系,所以,FG也是关系, 若彐x∈dom(FG),且x(FGy1和x(FG2,则 ≤x,y1∈FGA<x,y2∈FG t1(<x,t>∈F∧<t1,y1>∈G)A彐t2(<x,t2>∈F∧<t2,y2>∈G) 1彐t2(t1=t2∧<t1,y1>∈G∧<t2,y2>∈G (F为函数) →y1=y2 (G为函数) 所以,FG为函数 18
18 函数的复合 定理: 设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 ), 且x(F°G)y1和x(F°G)y2, 则 <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为函数
函数的复合 定理:设F和G是函数,则FG也是函数,且满足 (1)dom(F。G)={x| xeromA∧F(x) edong} (2)x∈dom(FG),有:FG(x)=G(F(x) 证明:(续) 任取x,x∈dom(FG) →3y(<x,t∈F∧<t,y>∈G) 彐t(x∈domF∧t=F(x) Atedomg) x∈{x| xedomF∧F(x) edong} 任取x,x∈domF∧F(x)∈domG 今<X,F(x)>∈F∧<F(x),G(F(x)>∈G <x,G(F(x)>∈FoG eDom (FoG)A FoG(x)=G(F(x)) 19 所以,(1)和(2)得证
19 函数的复合 证明: (续) 任取x, 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 } 任取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)) 所以, (1)和(2)得证. 定理: 设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))