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

1、數(shù)理邏輯Mathematical Logic 第一章 邏輯、集合和函數(shù)Chapter 1 Logic、set and function復(fù)習(xí)函數(shù)定義域、伴域、值域、像、原像單射、滿射、雙射反函數(shù)函數(shù)組合函數(shù)圖像底函數(shù)、頂函數(shù)復(fù)習(xí)序列算術(shù)序列幾何序列序列求和求和符號(hào)的下標(biāo)移位復(fù)習(xí)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 復(fù)習(xí)設(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ù)習(xí)證明：令f g是一個(gè)復(fù)合函數(shù) 若f g是滿射的，則f 是滿射的； 若f g是單射的，則g是單射的； 若f g是雙射的，則f 是滿射的，g是單射的；證明：設(shè)g: AB, f: BC (1)對(duì)C中的任意一個(gè)z，因?yàn)閒 g是滿射的，所以A中存在一個(gè)x使得f g(x)=z，則存在B中的一個(gè)元素y，使得g(x)=y并且f(y)=z，所以，存在y使得f(y)=z，f是滿射的；復(fù)習(xí)證

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

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

5、2+2x+1是O(x2)。因?yàn)橹灰獂1，就有x2+2x+1x2+2x2+x2=4x2根據(jù)大O的定義，取C=4，k=1所以f(x)是O(x2)；當(dāng)x2時(shí)，2xx2，x2+2x+1x2+x2+x2=3x2C=3，k=2一、大O符號(hào)若f(x)是O(g(x)，而對(duì)足夠大的x，h(x)是一個(gè)函數(shù)值的絕對(duì)值大于g(x)的函數(shù)，則有f(x)是O(h(x)。如果xk就有|f(x)|C|g(x)|，同時(shí)|h(x)|g(x)|對(duì)所有xk成立，那么當(dāng)xk時(shí)，|f(x)|C|h(x)|成立，于是f(x)是O(h(x)。一、大O符號(hà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符號(hào)在使用大O符號(hào)時(shí)，在f(x)是O(g(x)這一關(guān)系中，函數(shù)g總是選得盡可能?。ㄓ袝r(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符號(hào)f(x)=x2+2x+1g(x)=x2f(x)是O(g(x)并且g(x)是O(f(x)滿足上述兩個(gè)大O關(guān)系的函數(shù)f(x)和g(x)稱為同階的。一、大O符號(hào)f(x)是O(g(x)還可以寫作：f(x)=O(g(x)注意等號(hào)的含義：對(duì)于這些函數(shù)定義域

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

8、秀的程序員，就去讀第一卷，確定可以解決其中所有的問題。如果你能讀懂整套書的話，請(qǐng)給我發(fā)一份你的簡(jiǎn)歷?！币?、大O符號(hào)例：證明7x2是O(x3)。解：只要x7，7x2k，就有x3C(7x2 )，其等價(jià)于x7C，由于x可以任意大，所以不存在這樣的C；x3不是O(7x2)。一、大O符號(hào)多項(xiàng)式常用于估計(jì)函數(shù)的增長(zhǎng)；希望找到一個(gè)總是可以用來估計(jì)多項(xiàng)式增長(zhǎng)的結(jié)論；定理：令f(x)=anxn+an-1xn-1+a1x+a0，其中a0,a1,an-1,an為實(shí)數(shù)，那么f(x)是O(xn)。一、大O符號(hà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符號(hào)幾個(gè)與定義域?yàn)檎麛?shù)集合的函數(shù)有關(guān)的例子例：用O符號(hào)估計(jì)前n個(gè)正整數(shù)的和。解：由于前n個(gè)正整數(shù)都不超過n，所以 1+2+nn+n+n=n2 所以前n個(gè)正整數(shù)的和是O(n2)，其中C=1和k=1。一、大O符號(hào)n!=12 n；增長(zhǎng)迅速（n=20?）20!=2 432 902 008 176 640 000例：給出階乘函數(shù)和其對(duì)數(shù)的大O估計(jì)。解：乘積中的每一項(xiàng)都不超過n，所以

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

11、注意：|(f1+f2)(x)|=|f1(x)+f2(x)|f1(x)|+|f2(x)|二、函數(shù)組合的增長(zhǎng)當(dāng)x大于k1和k2時(shí)，有：|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時(shí)成立，其中k=max(k1,k2)。二、函數(shù)組合的增長(zhǎng)定理：假定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)。類似的方法可以推導(dǎo)出f1和f2的乘積的大O估計(jì)。二、函數(shù)組合的增長(zhǎng)當(dāng)xmax(k1,k2)時(shí)，我們有：|(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ù)組合的增長(zhǎng)定理：假定f1(x)是O(g1(x)，f2(x)是O(g2(x)，那么(f1f2)(x)是O(g1(x)g2(x)。用大O符號(hào)來估計(jì)函數(shù)的目的，是選一個(gè)相對(duì)增長(zhǎng)較慢的函數(shù)g(x)，使得f(x)是O(g(x)

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

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

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

16、+5x2+7是(x3)解：由于f(x)=8x3+5x2+78x3，對(duì)于所有正整數(shù)都成立，所以f(x)是(x3)。g(x)=x3是O(8x3+5x2+7)？x38x3+5x2+7，成立。三、大和大符號(hào)我們希望知道相對(duì)于一個(gè)簡(jiǎn)單參照函數(shù)而言，某函數(shù)增長(zhǎng)的階。要知道函數(shù)增長(zhǎng)的階，就需要了解函數(shù)大小的上界和下界。給定一個(gè)函數(shù)f(x)，我們想要一個(gè)參照函數(shù)g(x)，使得f(x)是O(g(x)和f(x)是(g(x)。三、大和大符號(hào)定義：令f和g為從整數(shù)集合或?qū)崝?shù)集合到實(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)通常是一個(gè)相對(duì)簡(jiǎn)單的參考函數(shù)。三、大和大符號(hào)例：前n個(gè)正整數(shù)的和是O(n2)，這個(gè)和是n2階的嗎？令f(n)=1+2+3+n，只需要找到C使得對(duì)足夠大的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)。三、大和大符號(hào)如果能找到正實(shí)數(shù)C1，C2和k，使得對(duì)xk，C1|g(x)|f(x)|C2|g(x)|，則f(x)是(g(x)。例：證明f(x)=3x2+8xlog

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