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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 8 รุ่นระหว่างกลางโดยผู้ใช้ 3 คน)
แถว 3: แถว 3:
 
<table cellpadding="5">
 
<table cellpadding="5">
 
<tr>
 
<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^2 \,</math></td>
 
<td align="center"><math> n! \,</math></td>
 
<td align="center"><math> n! \,</math></td>
แถว 29: แถว 29:
 
<td align="center"><math> (n+1)!\,</math></td>
 
<td align="center"><math> (n+1)!\,</math></td>
 
<td align="center"><math> \sqrt{\ln n} \,</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> n \,</math></td>
 
<td align="center"><math> 2^n \,</math></td>
 
<td align="center"><math> 2^n \,</math></td>
 
<td align="center"><math> n \ln n \,</math></td>
 
<td align="center"><math> n \ln n \,</math></td>
 
</tr></table>
 
</tr></table>
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 1|เฉลย]]
  
 
== ข้อ 2 ==
 
== ข้อ 2 ==
แถว 57: แถว 59:
 
# <math>T(n) = T(\sqrt{n}) + 1 \,</math>
 
# <math>T(n) = T(\sqrt{n}) + 1 \,</math>
 
# <math>T(n) = 3T(n/2) + n \log n \,</math>
 
# <math>T(n) = 3T(n/2) + n \log n \,</math>
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 3|เฉลย]]
  
 
== ข้อ 4 ==
 
== ข้อ 4 ==
แถว 75: แถว 79:
  
 
จงหา Big-Theta ของ <math>T(n) \,</math>
 
จงหา Big-Theta ของ <math>T(n) \,</math>
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ /เฉลยข้อ 4|เฉลย]]
  
 
== ข้อ 5 ==
 
== ข้อ 5 ==
แถว 93: แถว 99:
  
 
จงหา Big-Theta ของ <math>T(n) \,</math>
 
จงหา Big-Theta ของ <math>T(n) \,</math>
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 5|เฉลย]]
  
 
== ข้อ 6 ==
 
== ข้อ 6 ==
แถว 106: แถว 114:
 
       for j = 1 to k do
 
       for j = 1 to k do
 
         Call A(k)
 
         Call A(k)
 +
      do something in O(n) time
 
   }
 
   }
 
  }
 
  }
  
 
จงหา Big-Theta ของ <math>T(n) \,</math>
 
จงหา Big-Theta ของ <math>T(n) \,</math>
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 6|เฉลย]]

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

ข้อ 1

[CLRS 2-3] จงเรียงฟังก์ชันเหล่านี้ เพื่อทำให้ถ้าฟังก์ชัน มาก่อน แล้ว

เฉลย

ข้อ 2

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

  1. ถ้า แล้ว ด้วย
  2. ถ้า แล้ว
  3. ถ้า แล้ว

เฉลย

ข้อ 3

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

เฉลย

ข้อ 4

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

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

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

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

เฉลย