204512-53/lecture1

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

บันทึกคำบรรยายวิชา 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. จองพื้นที่เพิ่มสำหรับใส่ของ
  4. ลองวิเคราะห์การจองที่ใส่ของเพิ่มที่ละ 1 ที่

จากภาพการเก็บวิเคราะห์ได้ว่า การเก็บข้อมูลตัวที่ i

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

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

=  หน่วย
=  หน่วย
=  หน่วย

ดังนั้นการถ้ามีข้อมูล n ตัวจะได้ว่าต้องใช้ หน่วย


Tree.png