Time และ Space Complexity ในโครงสร้างข้อมูล

Algorithm Analysis (การวิเคราะห์อัลกอริทึม)

วิเคราะห์ประสิทธิภาพได้ 2 ช่วง:

• A Priori Analysis (ทฤษฎี): วิเคราะห์ก่อนเขียนโค้ด สมมติ Factor ภายนอก (CPU speed) คงที่
• A Posteriori Analysis (ทดลองจริง): เขียนโค้ดรันจริง วัด Running Time และ Memory จริง

Algorithm Complexity (ความซับซ้อนของอัลกอริทึม)

X = อัลกอริทึม, N = ขนาด Input
2 ปัจจัยหลัก: Time Factor และ Space Factor

Time Factor

นับจำนวน Key Operations (เช่น การเปรียบเทียบใน Sorting)

Space Factor

นับ Maximum Memory Space ที่อัลกอริทึมต้องการ

Complexity f(N) = Running Time และ/หรือ Storage Space ที่ต้องการ เทียบกับขนาด Input N

Space Complexity (ความซับซ้อนด้านพื้นที่)

หน่วยความจำที่อัลกอริทึมใช้ตลอดชีวิต =

1. Fixed Part: ตัวแปรคงที่, ขนาดโปรแกรม, ค่าคงที่ - ไม่ขึ้นกับขนาดปัญหา
2. Variable Part: ขึ้นกับขนาดปัญหา - Recursion Stack, Dynamic Allocation

S(p) = A + S_p(I) โดย A = Fixed Part, S_p(I) = Variable Part ขึ้นกับ Instance I

ตัวอย่าง: SUM(P, Q)

Step 1: START
Step 2: R ← P + Q + 10
Step 3: STOP

ตัวแปร: P, Q, R (3 ตัว) + ค่าคงที่ 1 → S(p) = 1 + 3 = 4 หน่วย (คูณด้วยขนาด Data Type)

Time Complexity (ความซับซ้อนด้านเวลา)

เวลาที่อัลกอริทึมใช้รันจนเสร็จ แทนด้วย t(N) = จำนวน Steps (แต่ละ Step ใช้เวลาคงที่)

ตัวอย่าง: บวกจำนวนเต็ม n-bit

ใช้ n Steps → t(N) = c × n (c = เวลาบวก 1 bit) → Linear Growth O(n)

สรุป Big-O Notation พบบ่อย