數(shù)理邏輯-第一章-邏輯、集合和函數(shù)-函數(shù)增長

1、數(shù)理邏輯Mathematical Logic 第一章 邏輯、集合和函數(shù)Chapter 1 Logic、set and function復習函數(shù)定義域、伴域、值域、像、原像單射、滿射、雙射反函數(shù)函數(shù)組合函數(shù)圖像底函數(shù)、頂函數(shù)復習序列算術(shù)序列幾何序列序列求和求和符號的下標移位復習1, 5, 11, 27, 65, 157, 379, 915 an=2 an-1+an-2; a0=1, a1=5. 0,2,10,30,68,130,222 n3+n 復習設(shè)X=1,2,3，Y=p,q，Z=a,b，f=(1,p),(2,p),(3,p)，g=(p,b),(q,b)，求gf 解：f: XY, g: YZ,

2、 gf: XZ gf=g(f(x) gf (1)=g(f(1)=g(p)=b; gf (2)=g(f(2)=g(p)=b; gf (2)=g(f(2)=g(p)=b; 所以， gf =(1,b), (2,b), (3,b)。復習證明：令f g是一個復合函數(shù) 若f g是滿射的，則f 是滿射的； 若f g是單射的，則g是單射的； 若f g是雙射的，則f 是滿射的，g是單射的；證明：設(shè)g: AB, f: BC (1)對C中的任意一個z，因為f g是滿射的，所以A中存在一個x使得f g(x)=z，則存在B中的一個元素y，使得g(x)=y并且f(y)=z，所以，存在y使得f(y)=z，f是滿射的；復習證

3、明：設(shè)g: AB, f: BC (2)對g的值域中的任意y，若存在x1,x2屬于A，使得g(x1)=g(x2)=y，對于這個y存在C中的元素z，使得f(y)=z，則f(g(x1)=f(g(x2)=z，又因為f g是單射，故x1=x2，所以g是單射的。 (3) 由(1),(2)得證。當f g是滿射的，g不一定是滿射的；當f g是單射的，f 不一定是單射的。1.8 函數(shù)增長The Growth of Functions一、大O符號一個計算機程序?qū)嵱眯缘闹匾蛩刂皇怯嬎銠C要花多長時間才能運算完成。如將n個整數(shù)按照增序排列為n個整數(shù)重新排序所需要的時間小于f(n)微秒，其中f(n)=100nlogn

4、+25n+9要分析此程序的實用性，我們需要了解當n增長時，這一函數(shù)增長得多快常用一個專門的符號來描述函數(shù)增長一、大O符號定義：令f和g為從整數(shù)集合或?qū)崝?shù)集合到實數(shù)集合的函數(shù)。我們說f(x)是O(g(x)，如果有常數(shù)C和k，使得只要xk，就有 |f(x)|C|g(x)|O(g(x)讀作f(x)是大O g(x)一、大O符號注意：要證明f(x)是O(g(x)，只要找到一對C和k，使得只要xk就有|f(x)|C|g(x)|。定義中要求的一對C和k不是唯一的。只要有一對這樣的數(shù)存在，就有無窮多這樣的數(shù)對；若C,k是這樣的一對，那么只要C1,k1滿足CC1，kk1k的x成立一、大O符號例：證明f(x)=x

5、2+2x+1是O(x2)。因為只要x1，就有x2+2x+1x2+2x2+x2=4x2根據(jù)大O的定義，取C=4，k=1所以f(x)是O(x2)；當x2時，2xx2，x2+2x+1x2+x2+x2=3x2C=3，k=2一、大O符號若f(x)是O(g(x)，而對足夠大的x，h(x)是一個函數(shù)值的絕對值大于g(x)的函數(shù)，則有f(x)是O(h(x)。如果xk就有|f(x)|C|g(x)|，同時|h(x)|g(x)|對所有xk成立，那么當xk時，|f(x)|C|h(x)|成立，于是f(x)是O(h(x)。一、大O符號f(x)=x2+2x+1是O(x2)，x2可以被函數(shù)值大于x2的任何函數(shù)取代；f(x)是

6、O(x3)f(x)是O(x2+2x+7)等等x2是O(x2+2x+1)也成立一、大O符號在使用大O符號時，在f(x)是O(g(x)這一關(guān)系中，函數(shù)g總是選得盡可能小（有時選自某個參考函數(shù)集合）常用的有：g(x)=1；g(x)=logx； g(x)=nlogx；g(x)=x； g(x)=x2；g(x)=xn ；g(x)=nx ； g(x)=x!一、大O符號f(x)=x2+2x+1g(x)=x2f(x)是O(g(x)并且g(x)是O(f(x)滿足上述兩個大O關(guān)系的函數(shù)f(x)和g(x)稱為同階的。一、大O符號f(x)是O(g(x)還可以寫作：f(x)=O(g(x)注意等號的含義：對于這些函數(shù)定義域

7、中足夠大的數(shù)而言，函數(shù)f和g的之間有個不等式關(guān)系成立。巴赫曼1892年首次引入大O符號；大O符號有時也稱為蘭多符號；克努思（高德納）推進了大O符號的廣泛使用，他還引入了大和大符號。http:/www-/knuth/一、大O符號計算機程序設(shè)計藝術(shù)是Knuth一生中最重要的事業(yè)，他寫這本書的目的是“組織和總結(jié)所知道的計算機方法的相關(guān)知識，并打下堅實的數(shù)學、歷史基礎(chǔ)”。1974年圖靈獎。1999年底被美國科學家期刊（American Scientist）列為20世紀最佳12部學術(shù)專著之一。任何人發(fā)現(xiàn)書上的錯誤，都可以向他舉發(fā)，并領(lǐng)取 $2.56美金。比爾蓋茨在1995年說，“如果你認為你是一名真正優(yōu)

8、秀的程序員，就去讀第一卷，確定可以解決其中所有的問題。如果你能讀懂整套書的話，請給我發(fā)一份你的簡歷。”一、大O符號例：證明7x2是O(x3)。解：只要x7，7x2k，就有x3C(7x2 )，其等價于x7C，由于x可以任意大，所以不存在這樣的C；x3不是O(7x2)。一、大O符號多項式常用于估計函數(shù)的增長；希望找到一個總是可以用來估計多項式增長的結(jié)論；定理：令f(x)=anxn+an-1xn-1+a1x+a0，其中a0,a1,an-1,an為實數(shù)，那么f(x)是O(xn)。一、大O符號證：如果x1，我們有|f(x)|=|anxn+an-1xn-1+a1x+a0| |an|xn+|an-1|xn-

9、1+|a1|x+|a0| = xn(|an|+|an-1|/x+|a1|/xn-1+|a0|/xn) xn(|an|+|an-1|+|a1|+|a0|) = C xn其中C=|an|+|an-1|+|a1|+|a0|一、大O符號幾個與定義域為正整數(shù)集合的函數(shù)有關(guān)的例子例：用O符號估計前n個正整數(shù)的和。解：由于前n個正整數(shù)都不超過n，所以 1+2+nn+n+n=n2 所以前n個正整數(shù)的和是O(n2)，其中C=1和k=1。一、大O符號n!=12 n；增長迅速（n=20?）20!=2 432 902 008 176 640 000例：給出階乘函數(shù)和其對數(shù)的大O估計。解：乘積中的每一項都不超過n，所以

10、 n!=12 nnn n=nn 所以階乘函數(shù)是O(nn)。兩邊取對數(shù)log(n!)nlogn 階乘函數(shù)的對數(shù)是O(nlogn)一、大O符號P84 例6二、函數(shù)組合的增長許多算法都由兩個或更多獨立的子過程組成；其所需要的步數(shù)是這些子過程使用步數(shù)的和；用大O估計時，必須找出對每個子過程的估計，再把它們組合在一起。往往要估計兩個函數(shù)和與積的增長。二、函數(shù)組合的增長假定f1(x)是O(g1(x)，f2(x)是O(g2(x)；從大O符號的定義，有常數(shù)C1，C2，k1，k2，使得：當xk1時，|f1(x)|C1|g1(x)|，當xk2時，|f2(x)|C2|g2(x)|，要估計f1(x)和f2(x)的和，

11、注意：|(f1+f2)(x)|=|f1(x)+f2(x)|f1(x)|+|f2(x)|二、函數(shù)組合的增長當x大于k1和k2時，有：|f1(x)|+|f2(x)|C1|g1(x)|+C2|g2(x)| (C1+C2)|g(x)|=C|g(x)|其中C=C1+C2，g(x)=max(|g1(x)|,|g2(x)|)。所以，|(f1+f2)(x)|C|g(x)|在xk時成立，其中k=max(k1,k2)。二、函數(shù)組合的增長定理：假定f1(x)是O(g1(x)，f2(x)是O(g2(x)，那么(f1+f2)(x)是O(max(g1(x),g2(x)。推論：假定f1(x)和f2(x)都是O(g(x)，那

12、么(f1+f2)(x)也是O(g(x)。類似的方法可以推導出f1和f2的乘積的大O估計。二、函數(shù)組合的增長當xmax(k1,k2)時，我們有：|(f1f2)(x)|=|f1(x)|f2(x)|C1|g1(x)|C2|g2(x)|=C1C2|g1(x)g2(x)|=C1C2|(g1g2)(x)|=C|(g1g2)(x)|其中C=C1C2；f1(x)f2(x)是O(g1g2)。二、函數(shù)組合的增長定理：假定f1(x)是O(g1(x)，f2(x)是O(g2(x)，那么(f1f2)(x)是O(g1(x)g2(x)。用大O符號來估計函數(shù)的目的，是選一個相對增長較慢的函數(shù)g(x)，使得f(x)是O(g(x)

13、。例：給出f(n)=3nlog(n!)+(n2+3)logn的大O估計，其中n是一個正整數(shù)。二、函數(shù)組合的增長f(n)=3nlog(n!)+(n2+3)logn解：首先估計3nlog(n!)。我們知道3n是O(n)以及l(fā)og(n!)是O(nlogn)，所以3nlog(n!)是O(n2logn)；下一步估計(n2+3)logn。我們知道n2+3是O(n2)，logn是O(n)【見例6】，所以(n2+3)logn是O(n3)。二、函數(shù)組合的增長(n2+3)logn2n2lognn3 當n2時。因此(n2+3)logn是O(n2logn)。所以f(n)是O(n2logn)。二、函數(shù)組合的增長例：給出

14、f(x)=(x+1)log(x2+1)+3x2的大O估計。解：首先找出(x+1)log(x2+1)的大O估計。 (x+1)是O(x)。 當x1時，x2+1x2+x2=2x2 ； log(x2+1)2時， log2+2logxlogx+2logx=3logx；二、函數(shù)組合的增長例：給出f(x)=(x+1)log(x2+1)+3x2的大O估計。解：因此，log(x2+1)是O(logx)； (x+1)log(x2+1)是O(xlogx)；又3x2是O(x2)； 所以，f(x)是O(max(xlogx, x2)，又xlogx1時，于是f(x)是O(x2)。二、函數(shù)組合的增長做大O估計時常用的函數(shù)有：

15、1, logn, n, nlogn, n2, 2n, n!它們之間的關(guān)系是從左到右依次增大，當n無限增長時。P86 圖1-21。三、大和大符號大O符號廣泛用于描述函數(shù)的增長，但它有其局限性；如f(x)是O(g(x)，估計的是f(x)大小的一個上限；要估計f(x)的下限，那么我們使用大符號；要估計f(x)的上、下限時，使用大符號。三、大和大符號定義：令f和g為從整數(shù)集合或?qū)崝?shù)集合到實數(shù)集合的函數(shù)，我們說f(x)是(g(x)，如果存在正常數(shù)C和k，使得xk時，|f(x)|C|g(x)|讀作f(x)是大 g(x)。三、大和大符號f(x)是(g(x)當且僅當g(x)是O(f(x)。例：f(x)=8x3

16、+5x2+7是(x3)解：由于f(x)=8x3+5x2+78x3，對于所有正整數(shù)都成立，所以f(x)是(x3)。g(x)=x3是O(8x3+5x2+7)？x38x3+5x2+7，成立。三、大和大符號我們希望知道相對于一個簡單參照函數(shù)而言，某函數(shù)增長的階。要知道函數(shù)增長的階，就需要了解函數(shù)大小的上界和下界。給定一個函數(shù)f(x)，我們想要一個參照函數(shù)g(x)，使得f(x)是O(g(x)和f(x)是(g(x)。三、大和大符號定義：令f和g為從整數(shù)集合或?qū)崝?shù)集合到實數(shù)集合的函數(shù)。如果f(x)是O(g(x)并且f(x)是(g(x)，就說f(x)是(g(x)。讀作f(x)是大 g(x)。也稱f(x)是g(

17、x)階的。若f(x)是(g(x)，g(x)也是(f(x)。g(x)通常是一個相對簡單的參考函數(shù)。三、大和大符號例：前n個正整數(shù)的和是O(n2)，這個和是n2階的嗎？令f(n)=1+2+3+n，只需要找到C使得對足夠大的n，f(n)Cn2。1+2+3+nn/2+(n/2+1)+n n/2+n/2+n/2 = (n-n/2+1)n/2(n/2)(n/2)=n2/4所以，f(n)是(n2)；因此，f(n)是n2階的。記作f(n)是(n2)。三、大和大符號如果能找到正實數(shù)C1，C2和k，使得對xk，C1|g(x)|f(x)|C2|g(x)|，則f(x)是(g(x)。例：證明f(x)=3x2+8xlog

18、x是(x2)當x1時，8xlogx8x2， 3x2+8xlogxk時，|f(x)|C|g(x)|。f(x)=O(g(x)。f(x)是O(g(x)，其中g(shù)(x)可以用具有更大絕對值的函數(shù)替換。小結(jié)估計多項式增長f(x)=anxn+an-1xn-1+a1x+a0，其中a0,a1,an-1,an為實數(shù)，那么f(x)是O(xn)。常用的函數(shù)1, logn, n, nlogn, n2, 2n, n!在使用大O符號時，在f(x)是O(g(x)這一關(guān)系中，函數(shù)g(x)總是選得盡可能小。小結(jié)函數(shù)組合的增長假定f1(x)是O(g1(x)，f2(x)是O(g2(x)，那么(f1+f2)(x)是O(max(g1(x