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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย 'อินพุต: อะเรย์ที่เรียงแล้วจำนวน k อะเรย์ แต่ละอะเร…')
 
 
(ไม่แสดง 7 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 5: แถว 5:
 
วัตถุที่เราต้องตรวจสอบคือ สมาชิกแต่ละตัวในแต่ละอะเรย์ เงื่อนไขคือ อะเรย์สุดท้ายที่ใช้รวมต้องเรียงด้วย
 
วัตถุที่เราต้องตรวจสอบคือ สมาชิกแต่ละตัวในแต่ละอะเรย์ เงื่อนไขคือ อะเรย์สุดท้ายที่ใช้รวมต้องเรียงด้วย
  
== ข้อย่อย 1===
+
== ข้อย่อย 1==
 +
พิจารณาการรวมอะเรย์ดังต่อไปนี้
 +
:ขั้นตอนที่ 1 การรวมอะเรย์ที่เรียงแล้วขนาด <math> n \, </math> ตัวที่หนึ่ง เข้ากับอะเรย์ที่เรียงแล้วขนาด<math> n \,</math> ตัวที่สอง เวลาในการรวมจะเป็น <math> 2n \,</math>
 +
:ขั้นตอนที่ 2 การรวมอะเรย์ที่เรียงแล้วขนาด <math> 2n \, </math> จากขั้นตอนที่ 1 เข้ากับอะเรย์ที่เรียงแล้วขนาด<math> n \,</math> ตัวที่สาม เวลาในการรวมจะเป็น <math> 3n \,</math>
 +
:ขั้นตอนที่ k-1 การรวมอะเรย์ที่เรียงแล้วขนาด <math> (k-1)n \, </math> จากขั้นตอนที่ k-2 เข้ากับอะเรย์ที่เรียงแล้วขนาด<math> n \,</math> ตัวที่ k เวลาในการรวมจะเป็น <math> kn \,</math>
 +
:ดังนั้นเวลารวมทั้งหมดจะเป็น <math> 2n+3n+...+kn=O(nk^2) \,</math>
  
== ข้อย่อย 2===
+
== ข้อย่อย 2 ==
 +
แนวคิด จะทำคล้าย ๆ กับ merge sort ธรรมดา โดยการรวมจะรวมอะเรย์สองตัวที่มีขนาด <math> n \, </math> เข้าด้วยกันให้เป็นอะเรย์ที่มีขนาด <math> 2n \, </math> หลังจากนั้น รวมอะเรย์ที่มีขนาด <math> 2n \, </math> เข้าเป็นอะเรย์ที่มีขนาด  <math> 4n \, </math> ทำแบบนี้ไปเรื่อย ๆ จนได้อะเรย์ที่เรียงแล้ว และมีขนาดเป็น <math> kn \, </math>
 +
 
 +
ส่วนเวลาการทำงาน สามารถคิดได้ดังนี้ ในการรวมอะเรย์ที่มีขนาด <math> n \, </math> เข้าด้วยกันให้เป็นอะเรย์ที่มีขนาด <math> 2n \, </math> นั้น แต่ละคู่จะใช้เวลา <math> 2n=O(n) \,</math> ซึ่งมีทั้งหมด <math> k/2 \,</math> คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น <math> (k/2)O(n)=O(kn) \,</math> ส่วนชั้นที่สองที่เป็นการรวมอะเรย์ที่มีขนาด <math> 2n \, </math> เข้าเป็นอะเรย์ที่มีขนาด  <math> 4n \, </math> นั้น แต่ละคู่จะใช้เวลา <math> 4n=O(n) \,</math> ซึ่งมีทั้งหมด <math> k/4 \,</math> คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น <math> (k/4)O(n)=O(kn) \,</math> คิดแบบนี้ไปเรื่อย ๆ ก็จะได้เวลาการทำงานของแต่ละชั้นเป็น <math> O(nk) \,</math> ซึ่ง tree มีทั้งหมด <math> \log k \, </math> ชั้น ดังนั้นเวลาการทำงานทั้งหมด ก็จะเป็น <math> O(nk \log k) \,</math>
 +
 
 +
[[ไฟล์:mergeLog.JPG]]

รุ่นแก้ไขปัจจุบันเมื่อ 07:48, 4 กันยายน 2552

อินพุต: อะเรย์ที่เรียงแล้วจำนวน k อะเรย์ แต่ละอะเรย์มีสมาชิกอยู่ ตัว

เอาพุต: รวมอะเรย์ที่เป็นอินพุตให้เป็นอะเรย์ที่เรียงแล้วขนาด ช่อง

วัตถุที่เราต้องตรวจสอบคือ สมาชิกแต่ละตัวในแต่ละอะเรย์ เงื่อนไขคือ อะเรย์สุดท้ายที่ใช้รวมต้องเรียงด้วย

ข้อย่อย 1

พิจารณาการรวมอะเรย์ดังต่อไปนี้

ขั้นตอนที่ 1 การรวมอะเรย์ที่เรียงแล้วขนาด ตัวที่หนึ่ง เข้ากับอะเรย์ที่เรียงแล้วขนาด ตัวที่สอง เวลาในการรวมจะเป็น
ขั้นตอนที่ 2 การรวมอะเรย์ที่เรียงแล้วขนาด จากขั้นตอนที่ 1 เข้ากับอะเรย์ที่เรียงแล้วขนาด ตัวที่สาม เวลาในการรวมจะเป็น
ขั้นตอนที่ k-1 การรวมอะเรย์ที่เรียงแล้วขนาด จากขั้นตอนที่ k-2 เข้ากับอะเรย์ที่เรียงแล้วขนาด ตัวที่ k เวลาในการรวมจะเป็น
ดังนั้นเวลารวมทั้งหมดจะเป็น

ข้อย่อย 2

แนวคิด จะทำคล้าย ๆ กับ merge sort ธรรมดา โดยการรวมจะรวมอะเรย์สองตัวที่มีขนาด เข้าด้วยกันให้เป็นอะเรย์ที่มีขนาด หลังจากนั้น รวมอะเรย์ที่มีขนาด เข้าเป็นอะเรย์ที่มีขนาด ทำแบบนี้ไปเรื่อย ๆ จนได้อะเรย์ที่เรียงแล้ว และมีขนาดเป็น

ส่วนเวลาการทำงาน สามารถคิดได้ดังนี้ ในการรวมอะเรย์ที่มีขนาด เข้าด้วยกันให้เป็นอะเรย์ที่มีขนาด นั้น แต่ละคู่จะใช้เวลา ซึ่งมีทั้งหมด คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น ส่วนชั้นที่สองที่เป็นการรวมอะเรย์ที่มีขนาด เข้าเป็นอะเรย์ที่มีขนาด นั้น แต่ละคู่จะใช้เวลา ซึ่งมีทั้งหมด คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น คิดแบบนี้ไปเรื่อย ๆ ก็จะได้เวลาการทำงานของแต่ละชั้นเป็น ซึ่ง tree มีทั้งหมด ชั้น ดังนั้นเวลาการทำงานทั้งหมด ก็จะเป็น

MergeLog.JPG