418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ

ข้อ 1

[CLRS 2-3] จงเรียงฟังก์ชันเหล่านี้ เพื่อทำให้ถ้าฟังก์ชัน $f(n)\,$ มาก่อน $g(n)\,$ แล้ว $f(n)=O(g(n))\,$

$({\sqrt {2}})^{\log _{2}n}\,$	$n^{2}\,$	$n!\,$	$(3/2)^{n}\,$	$n^{3}\,$	$\ln ^{2}n\,$
$\ln \ln n\,$	$\ln(n!)\,$	$2^{2^{n}}\,$	$n^{1/\ln n}\,$	$n\cdot 2^{n}\,$	$n^{\ln \ln n}\,$
$\ln n\,$	$1\,$	$2^{\log _{2}n}\,$	$(\ln n)^{\ln n}\,$	$e^{n}\,$	$4^{\log _{2}n}\,$
$(n+1)!\,$	${\sqrt {\ln n}}\,$	$2^{{\sqrt {2}}\log _{2}n}\,$	$n\,$	$2^{n}\,$	$n\ln n\,$

เฉลย

ข้อ 2

[CLRS 2-4] ให้ $f(n)\,$ และ $g(n)\,$ เป็นฟังก์ชันบวกใดๆ จงพิสูจน์หรือไม่ก็แสดงว่าข้อความต่อไปนี้ไม่เป็นความจริงด้วยการแสดงข้อขัดแย้ง

1. ถ้า $f(n)=O(g(n))\,$ แล้ว $g(n)=O(f(n))\,$ ด้วย
2. $f(n)+g(n)=O(\min(f(n),g(n)))\,$
3. ถ้า $f(n)=O(g(n))\,$ แล้ว $2^{f(n)}=O(2^{g(n)})\,$
4. $f(n)=O((f(n))^{2})\,$
5. ถ้า $f(n)=O(g(n))\,$ แล้ว $g(n)=\Omega (f(n))\,$
6. $f(n)=\Theta (f(n/2))\,$

เฉลย

ข้อ 3

[CLRS 4-1] จงหา Big-Theta ของฟังก์ชันต่อไปนี้

1. $T(n)=2T(n/2)+n^{3}\,$
2. $T(n)=T(9n/10)+n\,$
3. $T(n)=16T(n/4)+n^{2}\,$
4. $T(n)=7T(n/3)+n^{2}\,$
5. $T(n)=7T(n/2)+n^{2}\,$
6. $T(n)=2T(n/4)+{\sqrt {n}}\,$
7. $T(n)=T(n-1)+n\,$
8. $T(n)=T({\sqrt {n}})+1\,$
9. $T(n)=3T(n/2)+n\log n\,$

เฉลย

ข้อ 4

ให้ $T(n)\,$ เป็นเวลาการทำงานของอัลกอริทึมต่อไปนี้

Algorithm A(n)
{
  if (n <= 1)
    do something in O(1) time.
  else
  {
    do something in O(n) time.
    Call A(n/2).
    Call A(n/3).
    Call A(n/6).
  }
}

จงหา Big-Theta ของ $T(n)\,$

เฉลย

ข้อ 5

ให้ $T(n)\,$ เป็นเวลาการทำงานของอัลกอริทึมต่อไปนี้

Algorithm B(n)
{
  for i = 1 to n do
  {
    j = 1
    while (j < i)
    {
      j = 2*j
      do something in O(1) time
    }
  }
}

จงหา Big-Theta ของ $T(n)\,$

เฉลย

ข้อ 6

ให้ $T(n)\,$ เป็นเวลาการทำงานของอัลกอริทึมต่อไปนี้

Algorithm B(n)
{
  if (n < 1)
    do something in O(1) time
  else
  {
     let k = square root of n
     for j = 1 to k do
       Call A(k)
     do something in O(n) time
  }
}

จงหา Big-Theta ของ $T(n)\,$

เฉลย