提供一點我會的離散，看有沒有幫上什麼忙

------------------------------------------------------------

1.複查度分析

a.f(n)=O( g(n) )的涵義

存在c屬於R⁺，N₀屬於Z⁺，使得對於任何N>=N₀，均有f(n)<=c*g(n)

用白話來說，就是有一個函數的複雜度是f(n)，有一個函數的複雜度是g(n)

那問誰是誰的上界，上界這個不好定義，簡單的說

就好像f(n)=n+2，而g(n)=2*n

而我帶入n=1則會得到f(1)=3而g(1)=2

那你會得到f(1)>g(1)，你會說這樣不對阿~不是應該是f(n)<=g(n)嗎?

其實是這樣的，或許你帶入n=1會這樣，可是當我帶入n=2以後

你會發現都是g(n)比f(n)大，所以最後你就會寫

存在c=1，N₀=2，使得對於N>=2(就是N₀)，均有f(n)<=1*g(n)(也就是原始定義f(n)<=c*g(n))

那個N₀通常都是指g(n)將n帶入多少開始，就會比f(n)大的值

所以才會寫說使得對於任何N>=N₀，這個是基本定義

然後要判別是Big-O多少這應該不難吧~

所以f(n)=O(g(n) )=O(n)

b.f(n)=Ω( g(n) )的涵義

跟上面同理

存在c屬於R⁺，N₀屬於Z⁺，使得對於任何N>=N₀，均有f(n)>=c*g(n)

只差在今天反而是找n到多少的時候，就會比g(n)大

你可以把上面的例子反過來看，f(n)=2*n，g(n)=n+2

則

存在c=1，N₀=2，使得對於N>=2(就是N₀)，均有f(n)>=1*g(n)(也就是原始定義f(n)>=c*g(n))

所以f(n)=Ω( g(n) )=Ω( n )

c.f(n)=Θ( g(n) )的涵義

這個就比較特殊了，不難

先看原始定義

存在c₁、c₂屬於R⁺，N₀屬於Z⁺，使得對於任何N>=N₀，均有c₁*g(n)<=f(n)<=c₂*g(n)

有點像上面兩個的終合體

同樣f(n)=n+2、g(n)=2*n

則

存在c₁=1、c₂=1/2，N₀=2，使得對於N>=2(就是N₀)，均有1*g(n)<=f(n)<=1*g(n)(也就是原始定義c₁*g(n)<=f(n)<=c₂*g(n))

再清楚一點，就是1/2*(2*n) <= n+2 <= 1*(2*n) 當n大於等於2的時候

(如果這邊你跟我說n=1的時候，前面1/2*(2*n) <= n+2符合，是沒錯，但是要連後面n+2 <= 1*(2*n) 也要符合才可以

所以才會說N>=2的時候)

這樣就找到f(n)=Θ( g(n) )=Θ( n )

上面這三個是基本概念，所以最好是盡量理解

寫答案的時候就照這個步驟寫，你找到的c、N₀、...etc，都要一步一步寫出來，這樣老師要給分才好給

不要直接就寫答案，就f(n)=O( g(n) )，這樣通常是沒意義的，除非有特別交代

這是基本概念，再來是比較有技巧性的解題法