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

รุ่นแก้ไขปัจจุบันเมื่อ 14:58, 2 สิงหาคม 2552

เนื้อหา

1 ข้อ 1
2 ข้อ 2
3 ข้อ 3
4 ข้อ 4
5 ข้อ 5
6 ข้อ 6

ข้อ 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)\,$ เป็นฟังก์ชันบวกใดๆ จงพิสูจน์หรือไม่ก็แสดงว่าข้อความต่อไปนี้ไม่เป็นความจริงด้วยการแสดงข้อขัดแย้ง

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

เฉลย

ข้อ 3

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

$T(n)=2T(n/2)+n^{3}\,$
$T(n)=T(9n/10)+n\,$
$T(n)=16T(n/4)+n^{2}\,$
$T(n)=7T(n/3)+n^{2}\,$
$T(n)=7T(n/2)+n^{2}\,$
$T(n)=2T(n/4)+{\sqrt {n}}\,$
$T(n)=T(n-1)+n\,$
$T(n)=T({\sqrt {n}})+1\,$
$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)\,$

เฉลย

@@ แถว 1: / แถว 1: @@
 == ข้อ 1 ==
-[CLRS] จงเรียงฟังก์ชันเหล่านี้ เพื่อทำให้ถ้าฟังก์ชัน <math>f(n) \,</math> มาก่อน <math>g(n) \,</math> แล้ว <math>f(n) = O(g(n)) \,</math>
+[CLRS 2-3] จงเรียงฟังก์ชันเหล่านี้ เพื่อทำให้ถ้าฟังก์ชัน <math>f(n) \,</math> มาก่อน <math>g(n) \,</math> แล้ว <math>f(n) = O(g(n)) \,</math>
 <table cellpadding="5">
 <tr>
-<td align="center"><math> (\sqrt{2})^{\ln n}\,</math></td>
+<td align="center"><math> (\sqrt{2})^{\log_2 n}\,</math></td>
 <td align="center"><math> n^2 \,</math></td>
 <td align="center"><math> n! \,</math></td>
@@ แถว 29: / แถว 29: @@
 <td align="center"><math> (n+1)!\,</math></td>
 <td align="center"><math> \sqrt{\ln n} \,</math></td>
-<td align="center"><math> 2^{\sqrt 2 \ln  n} \,</math></td>
+<td align="center"><math> 2^{\sqrt 2 \log_2  n} \,</math></td>
 <td align="center"><math> n \,</math></td>
 <td align="center"><math> 2^n \,</math></td>
 <td align="center"><math> n \ln n \,</math></td>
 </tr></table>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 1|เฉลย]]
+== ข้อ 2 ==
+[CLRS 2-4] ให้ <math>f(n) \,</math> และ <math>g(n)\,</math> เป็นฟังก์ชันบวกใดๆ จงพิสูจน์หรือไม่ก็แสดงว่าข้อความต่อไปนี้ไม่เป็นความจริงด้วยการแสดงข้อขัดแย้ง
+# ถ้า <math>f(n) = O(g(n)) \,</math> แล้ว <math>g(n) = O(f(n))\,</math> ด้วย
+# <math>f(n) + g(n) = O(\min(f(n), g(n))) \,</math>
+# ถ้า <math>f(n) = O(g(n))\,</math> แล้ว <math>2^{f(n)} = O(2^{g(n)}) \,</math>
+# <math>f(n) = O((f(n))^2)\,</math>
+# ถ้า <math>f(n) = O(g(n)) \,</math> แล้ว <math>g(n) = \Omega(f(n)) \,</math>
+# <math>f(n) = \Theta(f(n/2))\,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 2|เฉลย]]
+== ข้อ 3 ==
+[CLRS 4-1] จงหา Big-Theta ของฟังก์ชันต่อไปนี้
+# <math>T(n) = 2T(n/2) + n^3 \,</math>
+# <math>T(n) = T(9n/10) + n \,</math>
+# <math>T(n) = 16T(n/4) + n^2 \,</math>
+# <math>T(n) = 7T(n/3) + n^2 \,</math>
+# <math>T(n) = 7T(n/2) + n^2 \,</math>
+# <math>T(n) = 2T(n/4) + \sqrt{n} \,</math>
+# <math>T(n) = T(n-1) + n \,</math>
+# <math>T(n) = T(\sqrt{n}) + 1 \,</math>
+# <math>T(n) = 3T(n/2) + n \log n \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 3|เฉลย]]
+== ข้อ 4 ==
+ให้ <math>T(n) \,</math> เป็นเวลาการทำงานของอัลกอริทึมต่อไปนี้
+ 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 ของ <math>T(n) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ /เฉลยข้อ 4|เฉลย]]
+== ข้อ 5 ==
+ให้ <math>T(n) \,</math> เป็นเวลาการทำงานของอัลกอริทึมต่อไปนี้
+ 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 ของ <math>T(n) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 5|เฉลย]]
+== ข้อ 6 ==
+ให้ <math>T(n) \,</math> เป็นเวลาการทำงานของอัลกอริทึมต่อไปนี้
+ 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 ของ <math>T(n) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 6|เฉลย]]

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

รุ่นแก้ไขปัจจุบันเมื่อ 14:58, 2 สิงหาคม 2552

เนื้อหา

ข้อ 1

ข้อ 2

ข้อ 3

ข้อ 4

ข้อ 5

ข้อ 6

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ