如何證明漸近不縮

Question

我要證明下面的語句

2^(⌊lg n⌋+⌈lg n⌉)∕n ∈ Θ(n) 

我知道，爲了證明這一點，我們必須找到常量c1>0，c2>0和n0>0這樣

c1.g(n) <= f(n) <= c2.g(n) for all n >= n0 

換句話說，我們必須證明f(n) <= c.g(n) and f(n) >= c.g(n)。

的問題是如何證明左側(2^(⌊lg n⌋+⌈lg n⌉)∕n)

謝謝

Answer 1

您可以通過擴大指數開始。它等於n1 * n2/n，其中n1 < = n < = n2,2 * n1> n且n * 2> n2。其餘的應該很容易。

Answer 2

下面是上界推導：

2^(⌊lg n⌋+⌈lg n⌉)/n 
= 2^(2⌊lg n⌋+1)/n 
<= 2^(2 lg n + 1)/n 
= 2^(2 lg n) 2^(1)/n 
= 2 n^2/n 
= 2 n 
= O(n) 

因此，我們知道你的函數可以通過以上2 * N爲界。現在我們做下限：

2^(⌊lg n⌋+⌈lg n⌉)/n 
= 2^(2⌈lg n⌉ - 1)/n 
>= 2^(2 lg n - 1)/n 
= 2^(2 lg n) 2^(-1)/n 
= 1/2 n^2/n 
= 1/2 n 
= O(n) 

我們現在知道你的函數可以被下面的n/2所限制。

檢查gnuplot;這些答案看起來很好，很緊張。這是純粹的代數解決方案，使用floor（）和ceiling（）函數的定義。