3.1 漸進(jìn)符號(hào)
3.1-1
假設(shè) )
與 )
都是漸進(jìn)非負(fù)函數(shù)跺株。使用 
記號(hào)的基本定義來(lái)證明 %2C%20g(n))%20%3D%20%5CTheta(f(n)%20%2B%20g(n)))
苍日。
因?yàn)? 與 都為漸進(jìn)非負(fù)的函數(shù)，所以根據(jù)定義针姿，有：
存在 
袱吆、
，使得：
所以处铛，我們?nèi)?
饲趋；此時(shí)，當(dāng) 
時(shí)撤蟆，同時(shí)有 %20%5Cgeq%200%2C%20g(n)%20%5Cgeq%200)
奕塑。
下面我們?nèi)?
，根據(jù) %2C%20g(n))
的漸進(jìn)非負(fù)保證家肯，當(dāng) 時(shí)龄砰，有：
%20%2B%20g(n)%7D%7B2%7D%20%5Cleq%20max%5C%7Bf(n)%2C%20g(n)%5C%7D%20%5Cleq%20f(n)%20%2B%20g(n))
所以，得證讨衣！换棚。
3.1-2
證明：對(duì)任意實(shí)常數(shù) 
和 
，其中 
反镇，有 %5Eb%20%3D%20%5CTheta(n%5Eb))
固蚤。
為了證明 ，我們需要找到常量 
歹茶，使得：
對(duì)于所有的 
夕玩，有 %5Eb%20%5Cleq%20c_2n%5Eb)
。
其中：
故惊豺，若 
燎孟。
易得，若 尸昧，有下列公式：
? %5Eb%20%5Cleq%20(n%20%2B%20a)%5Eb%20%5Cleq%20(2n)%5Eb)
揩页，即：
? %5Ebn%5Eb%20%5Cleq%20(n%20%2B%20a)%5Eb%20%5Cleq%202%5Ebn%5Eb)
。
故彻磁，取 %5Eb%2C%20c_2%20%3D%202%5Eb%2C%20n_0%20%3D%202%7Ca%7C)
碍沐，即可證明 。
3.1-3
解釋為什么“算法 A 的運(yùn)行時(shí)間至少是 )
”這一表述是無(wú)意義的衷蜓。
設(shè)運(yùn)行時(shí)間為 )
累提。則 %20%5Cgeq%20O(n%5E2))
代表：
對(duì)于任意的 %20%5Cin%20O(n%5E2)%2C%20T(n)%20%5Cgeq%20f(n))
。
也即 %20%5Cleq%20cn%5E2%EF%BC%8CT(n)%20%5Cgeq%20f(n))
斋陪。
這只能說(shuō)明 %20%5Cgeq%200)
這一無(wú)需證明的結(jié)論而已。
3.1-4
)
成立嗎置吓？)
成立嗎无虚？
-
，故：
對(duì)于任意的 
友题，易得 
戴质。
即 成立度宦。
-
反證法：若 成立踢匣，則對(duì) 
，有 
离唬；
又因?yàn)榇藭r(shí) 
，故有 
划鸽；
即 
输莺。顯然這與趨向無(wú)窮的 n 是相悖的，
故 不成立裸诽。
3.1-5
證明定理 3.1嫂用。
-
充分性：已知 %20%3D%20%5CTheta(g(n)))
，即存在 丈冬，使得：
? %20%5Cleq%20f(n)%20%5Cleq%20c_2g(n))
尸折。
故 %20%3D%20O(g(n)))
且 %20%3D%20%5COmega(g(n)))
养晋。
-
必要性：已知 旷太，則存在 
孙乖，使得：
? %20%5Cleq%20c_2g(n)%2C%20n%20%5Cgeq%20n_2)
；
且已知 粒梦，則存在 
，使得：
? %20%5Cleq%20f(n)%2C%20n%20%5Cgeq%20n_1)
荸实。
故匀们，取 
，有
? %20%5Cleq%20f(n)%20%5Cleq%20c_2g(n)%2C%20n%20%5Cgeq%20n_0)
准给。
于是可得：泄朴。
3.1-6
證明：一個(gè)算法的運(yùn)行時(shí)間為 ))
，則當(dāng)且僅當(dāng)其最壞情況運(yùn)行時(shí)間為 ))
露氮，且其最好情況運(yùn)行時(shí)間為 ))
祖灰。
由定義易可證， 記號(hào)漸進(jìn)地給出一個(gè)函數(shù)的上界及下界畔规，且可分別由 
和 
符號(hào)來(lái)表示其上下界局扶。相對(duì)的，該算法的最壞和最好情況的運(yùn)行時(shí)間也代表了該算法運(yùn)行時(shí)間的上下界叁扫。故得證三妈。
3.1-7
證明：)%20%5Cbigcap%20%5Comega(g(n)))
為空集。
設(shè) %20%5Cin%20(o(g(n))%20%5Cbigcup%20%5Comega(g(n))))
莫绣，也就代表著 %20%3D%20o(g(n)%20%3D%20%5Comega(g(n))))
畴蒲。則有：
很明顯，不成立对室。
3.1-8
可以擴(kuò)展我們的記號(hào)到有兩個(gè)參數(shù) 
和 
的情形模燥，其中的 和 可以按不同速率獨(dú)立地趨于無(wú)窮咖祭。對(duì)于給定的函數(shù) )
，用 ))
來(lái)表示以下函數(shù)集：
? )%20%3D%20%5C%7Bf(n%2C%20m))
：存在正常量 
和 
心肪，使得對(duì)所有 或 
，有 %20%5Cleq%20cg(n%2C%20m)%20%5C%7D)
纠吴。
對(duì) ))
和 ))
給出相應(yīng)的定義硬鞍。
-
)%20%3D%20%5C%7B%20f(n%2C%20m))
：存在正常量 和 戴已，使得對(duì)所有 或 固该，有 %20%5Cleq%20f(n%2C%20m)%20%5C%7D)
。
-
)%20%3D%20%5C%7Bf(n%2C%20m))
：存在正常量 
和 ，使得對(duì)所有 或 握联，有 %20%5Cleq%20f(n%2C%20m)%20%5Cleq%20c_2%20g(n%2C%20m)%20%5C%7D)
桦沉。
時(shí)搓幌，
杆故；
時(shí)，
溉愁。
