การเขียนโปรแกรมใดๆ ต้องพิจารณาถึงข้อจำกัดที่สำคัญของคอมพิวเตอร์ ดังนี้
- โปรแกรมที่เขียนนั้นใช้เนื้อที่ความจำมากน้อยแค่ไหน
- โปรแกรมนั้นมีอัลกอริทึ่มที่เร็วเพียงใด
เนื่องจากเป็นข้อจำกัดทางคอมพิวเตอร์ ดังนั้น จุดประสงค์หลักของการเขียนโปรแกรมที่ดี จึงมีเป้าหมายอยู่ที่ การได้โปรแกรมที่ทำงานได้เร็วที่สุดภายใต้การใช้เนื้อที่ความจำที่น้อยที่สุด กล่าวคือการใช้ทรัพยากรอย่างคุ้มค่านั่นเอง
กระบวนการวัด ที่นิยม มี 2 แบบ
- การวิเคราะห์เวลาที่ใช้ในการประมวลผล (Time Complexity Analysis)
- การวิเคราะห์หน่วยความจำที่ใช้ในการประมวลผล (Space Complexity Analysis)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
การวิเคราะห์เวลาที่ใช้ในการประมวลผล (Time Complexity Analysis)
การประเมินผลความเร็วของโปรแกรม หรือ อัลกอริทึ่ม สามารถประเมินได้ในรูปแบบของฟังก์ชั่น ที่เรียกกันว่า Big-O notation
** จริงๆ รายละเอียดมีเยอะกว่านั้น แต่ในที่นี้จะขอกล่าวถึงแค่ Big-O notation
Big-O notation
- ใช้ในการระบุทรัพยากรที่ใช้ในการทำงานของอัลกอรึทึ่ม เมื่อขนาดของข้อมูลรับเข้า (Input) เปลี่ยน ไป ซึ่งความหมายของทรัพยากรในที่นี้ จะหมายถึง เวลา กล่าวคือ เราจะสนใจความสัมพันธ์ระหว่าง เวลา กับ ขนาดของ Input หรือ อาจกล่าวได้อีกทางหนึ่งว่า หาก Input ที่มีขนาดใดขนาดหนึ่ง
(Input ข้อมูลรับเข้า ขนาด N) จะใช้เวลาในการทำงานมากที่สุด (Upper bound) เป็นเท่าไหร่ ซึ่ง
Big-O เป็นฟังก์ชันที่นิยมใช้มากที่สุดในการประเมินผลของอัลกอริทึ่ม
ความเร็วในการทำงานของแต่ละอัลกอริทึ่มที่พบได้บ่อย โดยเรียงจากเร็วไปช้า มีดังนี้
1. ความเร็วในการประมวลผลแบบฟังก์ชั่น ลอการิทึ่มมิก (Logarithmic)
O(log n)
2. ความเร็วในการประมวลผลแบบฟังก์ชั่น เส้นตรง (Linear)
O(n)
3. ความเร็วในการประมวลผลแบบ
O(n log n)
4. ความเร็วในการประมวลผลแบบฟังก์ชั่นกำลังสอง (Quadratic)
O(n^2)
5. ความเร็วในการประมวลผลแบบฟังก์ชั่นกำลังสาม (Cubic)
O(n^3)
6. ความเร็วในการประมวลผลแบบฟังก์ชั่นเอ็กซ์โปเนนเชียล (Exponential)
O(2^n)
การพิจารณาว่ามี Big-O แบบใดนั้น จะพิจารณาที่ฟังก์ชั่น f(n) ซึ่งเป็นแต่ละเทอมในการทำงาน
ตัวอย่าง
for (i=0; i<n; i++){
for (j=0; i<n; j++){
คำสั่ง A
}
}
จากตัวอย่าง เมื่อพิจารณาจะพบว่า คำสั่ง A จะถูกปฏิบัติ (Execute) ภายใต้ ลูป (Loop) i ที่ ถูกปฏิบัติ n ครั้ง และ ลูป j ที่ถูกปฏิบัติอีกจำนวณ n ครั้ง ดังนั้นคำสั่ง A จะถูกปฏิบัติภายใต้ เทอมการทำงาน n*n ครั้ง มี Big-O ที่มากที่สุดคือ O(n^2)
โดยเฉพาะเทอมที่ทำให้เกิด คอสท์ (Cost) สูงสุดในการทำงาน เช่น การทำซ้ำ หรือ ลูป (Loop)
ซึ่งมีหลายแบบ ดังนี้
1. ลูปเชิงเส้น (Linear Loop)
ตัวอย่าง
for (i=0; i<n; i++) -----> f(n) = n
for (i=0; i<n; i+=2) -----> f(n) = n/2
========================================================================
2. ลูปแบบลอการิทึ่มมิก (Logarithmic Loop)
ตัวอย่าง
for (i=0; i<; i*=2) ------> f(n) = log n
for (i=0; i<n; i/=2) ------> f(n) = log2n
========================================================================
3. ลูปแบบซ้อน (Nested Loop)
แบ่งเป็น
3.1 ลูปแบบซ้อนชนิดลอการิทึ่มเชิงเส้น (Linear Logarithmic Loop)
ตัวอย่าง
for (i=0; i<n; i++){ ------>f(n) = n
for(j=0; j<n; j*=2){ ------>f(n) log n
คำสั่ง A
}
}
ดังนั้น f(n) = n log n
--------------------------------------------------------------------------------------------------------------------------
3.2 ลูปแบบซ้อนชนิดกำลังสอง (Quadratic Loop)
ตัวอย่าง
for (i=0; i<n; i++){ ------>f(n) = n
for (j=0; j<n; j++){ ------>f(n) = n
คำสั่ง A
}
}
ดังนั้น f(n) = n^2
--------------------------------------------------------------------------------------------------------------------------
3.3 ลูปแบบซ้อนกำลังสองชนิดขึ้นต่อกัน (Dependent Quadratic)
ตัวอย่าง
for (i=0; i<n; i++){ ------>f(n) = n
for (j=0; j<i; j++){ ------>f(n) = n
คำสั่ง A
}
}
ดังนั้น f(n) = n((n+1)/2)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
การวิเคราะห์หน่วยความจำที่ใช้ในการประมวลผล (Space Complexity Analysis)
การวิเคราะห์หน่วยความจำทั้งหมดที่โปรแกรมใช้ในการประมวลนั้น เพื่อให้ทราบถึงขนาดข้อมูลที่สามารถป้อน หรือ ส่ง เข้ามาให้อัลกอริทึ่มประมวลผลแล้วไม่เกิดข้อผิดพลาด หรือเพื่อให้ทราบถึงขนาดหน่วยความจำของเครื่องคอมพิวเตอร์ว่ามีเพียงพอสำหรับการเก็บข้อมูลทั้งหมดในขณะทำการประมวลผลหรือไม่ มีประโยชน์อย่างมากเมื่อทำงานกำกับหน่วยความจำที่จำกัด เช่น การประมวลผลผ่านเครือข่าย การทำงานของโปรแกรมบนเครื่องมือถือที่มีทรัพยากรจำกัด เป็นต้น
องค์ประกอบในการวิเคราะห์แบ่งออกเป็น 3 ส่วน ดังนี้
1. Instruction Space
คือ ขนาดของหน่วยความจำที่จำเป็นต้องใช้ในขณะที่ คอมไพเลอร์ (Compiler) ทำการ คอมไพล์ (compile) โปรแกรม
2. Data Space
คือ ขนาดหน่วยความจำที่จำเป็นต้องใช้สำหรับเก็บข้อมูลค่าคงที่ และตัวแปรที่ใช้ขณะประมวลผลโปรแกรม แบ่งออกเป็น 2 ประเภท
2.1 Static memory ตัวอย่าง เช่น การประกาศขนาดของอาเรย์เพื่อจองพื้นที่หน่วยความจำ
2.2 Dynamic memory ตัวอย่าง เช่น พ้อยเตอร์ (Pointer) ในภาษา C หรือ ลิ้งค์ลิสต์ (Link list) ที่
สามารถเพิ่มหรือลดขนาดการเก็บข้อมูลได้แบบอัตโนมัติ โดยไม่ต้องประกาศจองพื้นที่หน่วย
ความจำ
3. Environment Stack Space
คือ หน่วยความจำที่ใช้สำหรับเก็บข้อมูลผลลัพท์ที่ได้จากการประมวลผล เพื่อรอเวลาที่จะนำกลับมาใช้ใหม่ในโปรแกรม ซึ่งหน่วยความจำประเภทนี้จะเกิดขึ้นเมื่อมีการใช้งานโปรแกรมเท่านั้น
ตัวอย่าง การวิเคราะห์หน่วยความจำที่ใช้ในการประมวลผล
int result
result = data1 + data2
จากตัวอย่าง มีการประกาศตัวแปรทั้งหมด 3 ตัวแปร
- result
- data1
- data2
ทั้งหมดถูกกำหนด ชนิด (Type) ให้ เป็น int (ตัวเลข Integer : int) ซึ่ง ชนิด ของข้อมูลจะใช้หน่วยความจำเท่าไหร่ขึ้นอยู่กับภาษาที่เขียน เช่น ภาษา C ใช้พื้นที่หน่วยความจำ 2 ไบต์ ภาษาจาวา ใช้พื้นที่หน่วยความจำ 4 ไบต์ ดังนั้น จากตัวอย่างนี้ มีตัวแปรทั้งหมด 3 ตัว ถ้าเป็น ภาษา C จะใช้หน่วยความจำ 3*2 = 6 ไบต์ และ ภาษาจาวา จะใช้หน่วยความจำ 3*4 = 12 ไบต์
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
อ้างอิง
1) บล็อกของอาจารย์ที่เคารพ thaiall :D
2) Scheguc News
3) หนังสือ : คู่มือเรียนโครงสร้างข้อมูล และ อัลกอริทึ่ม (Data Structure & Algorithm)
4) หนังสือโครงสร้างข้อมูลเพื่อการออกแบบโปรแกรมคอมพิวเตอร์
