204512-53/lecture1

บันทึกคำบรรยายวิชา 204512-53 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย: (กรุณาใส่ด้วย) Algorithm Lecture #1

Course Information

รายละเอียดวิชาสามารถดูได้ที่ http://www.cpe.ku.ac.th/~jtf/wiki/doku.php?id=01204512-53

เกณฑ์การให้คะแนน

• Homework 15%
• Project 15%
• Scribe Note 5%
• Mid-Term 2 Times 20*2%
• Final 25%

Introduction to Algorithm

ทำไมเราต้องวิเคราะห์อัลกอริทึม

• เพื่อความถูกต้องของอัลกอริทึม - ต้องการความแน่ใจ
• เพื่อประสิทธิภาพของอัลกอริทึม
  • เวลา (time)
  • พื้นที่ (space)
  • คุณภาพคำตอบ (quality)

เนื้อหาแต่ละบทที่จะสอน ตามลำดับ

1. Data Structure
2. Graph Algorithm
3. Dynamic Programming
4. Linear Programming
5. Randomize Algorithm

Data Structure

ตัวอย่างปัญหาที่ 1

การจองอาเรย์ให้เหมาะสมกับขนาดข้อมูลที่บรรจุ โดยกำหนดให้มีขั้นตอน การทำงานดังนี้

1. จองพื้นที่สำหรับใส่ของ
2. นำของไปใส่จนเต็ม
3. จองพื้นที่เพิ่มสำหรับใส่ของ

กรณี 1: จองแบบเพิ่มทีละ 1 ที่

จากภาพการเก็บ สามารถวิเคราะห์ได้ว่า

• การจองใช้เวลา 1 หน่วย
• การคัดลอกต้องคัดลอก i - 1 ตัวดังนั้นใช้เวลา i - 1 หน่วย
• การนำข้อมูลใหม่ไปใส่ใช้เวลาอีก 1 หน่วย

จะเห็นได้ว่าในการสร้างอาเรย์เก็บข้อมูล n ตัวจะต้องใช้เวลาทั้งหมด

= $2+3+4+...+n+n+1$ หน่วย
= $2+3+4+...+n+n+1$ หน่วย
= $(1+2+3+...+n)+n$ หน่วย

ดังนั้นการถ้ามีข้อมูล n ตัวจะได้ว่าต้องใช้ ${\frac {n*(n+1)+n}{2}}$ หน่วย หรือ O($n^{2}$)

กรณี 2: จองแบบเพิ่มทีละ 3 ที่

จากภาพการเก็บ สามารถวิเคราะห์ได้ว่าจะยังได้ผลลัพธ์ไม่ต่างจากเดิมมาก คือ O($n^{2}$) โดย n ในที่นี้เทียบได้กับ ${\frac {n}{3}}$ ของตัวอย่างบน มาจาก $n+3*{\frac {n*(n+1)}{2}}+3*n$ ซึ่งมี factor 3 เพิ่มเข้ามา

กรณี 3: จองแบบเพิ่มทีละ $2^{k}$ ที่

ต่อมามีคนเสนอว่าถ้าลองจองเป็นแบบ $2^{k}$ โดยที่ k หมายถึงการจองครั้งที่ k และค่า k เริ่มต้นจาก 0 เพื่อเป็นการตัดปัญหา ว่ากรณ๊ถ้าจองไม่เต็มจะทำอย่างไร เราจึงสมมุติไปเลยว่าการจองที่ n นั้นจะต้องจอง $n=2^{k}$ โดย k นั้นคือเลขจำนวนเต็มใดๆที่มากกว่า 0 ซึ่งถ้า $n<2^{k}$ อาจหมายถึงการแถมเวลาให้เต็ม $n=2^{k}$ เลยก็ได้

จากภาพการเก็บ สามารถวิเคราะห์ได้ว่า

• จะได้ว่ามีการจองข้อมูลเกิดขึ้นทั้งหมด k ครั้ง
• มีการเขียนข้อมูล $n(2^{k})$ ครั้ง
• มีการคัดลอกข้อมูล $1+2+4+8+...+2^{k-1}=(2^{k})-1$ (มองง่ายๆให้มองเป็นการบวกเลข binary)

ดังนั้นจะได้ k$+2^{k}+2^{k}-1=O(n)$