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

ข้อ 1

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

Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 762795351 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Thu, 22 Jan 2026 16:32:43 GMT Sensitive client information IP address: 158.108.32.49 $({\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}}\,$		$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. ถ้า แล้ว $2^{f(n)}=O(2^{g(n)})\,$
4. $f(n)=O((f(n))^{2})\,$
5. ถ้า แล้ว $g(n)=\Omega (f(n))\,$

เฉลย

ข้อ 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}\,$
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\,$

เฉลย

ข้อ 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 ของ

เฉลย

ข้อ 5

ให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 799386047
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Thu, 22 Jan 2026 16:32:51 GMT


Sensitive client information

IP address: 158.108.32.49

$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 ของ

เฉลย

ข้อ 6

ให้ เป็นเวลาการทำงานของอัลกอริทึมต่อไปนี้

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)\,$

เฉลย