Time Complexity กับ Asymptotic notation (Big O) สิ่งที่ Software Engineer ควรรู้
สวัสดีผู้อ่านทุกท่านครับวันนี้ผมจะพาไปทบทวนบทเรียน เกี่ยวกับเรื่อง Time Complexity และ Asymptotic notation ในส่วนของ Big O notation โดยผมคิดว่าใครที่อยู่ในสายคอมพิวเตอร์ หรือนักคณิตศาสตร์คงจะทราบกันดีอยู่แล้ว ว่าสิ่งนี้มันมีประโยชน์กับเรามาก สำหรับในงานสายคอมพิวเตอร์สามารถนำมาใช้ลดต้นทุนของหน่วยการประมวลผล รวมถึงลดเวลาในการทำงานทำให้เกิดประโยชน์ต่อทุกฝ่ายได้อย่างมาก เอาเป็นว่าไม่อยากชมเยอะ ไปดูกันดีกว่า
การพัฒนาซอฟแวร์ ไม่ใช่สักแต่ว่าทำให้มันรันได้ ควรจะทำให้มันมีคุณภาพด้วย
Time Complexity
Time Complexity ใน Computer Science, Computer Engineer หรือ Related IT Field คือความซับซ้อนของการคำนวณที่จะอธิบายระยะเวลาที่ใช้ในการเรียกใช้ Algorithm หรือ Logic ที่ถูกเขียนขึ้นมา.. ถ้าให้แปลเป็นไทยแบบตรงไปตรงมาก็คือ “ความซับซ้อนของเวลา” เป็นไงครับพอแปลเป็นไทยแล้วดูยากเข้าไปอีก ฮ่า ๆ
กล่าวคือตั้งแต่ Algorithm ทำงาน เวลาในการทำงานอาจแตกต่างกันไปตามขนาด Input ที่ต่างกัน โดยทั่วไปจะพิจารณาจากความซับซ้อนของระยะเวลาที่แย่ที่สุด (worst-case complexity) ซึ่งเป็นระยะเวลาสูงสุดที่จำเป็นสำหรับ Input ที่มีขนาดที่กำหนด เรามักใช้ Asymptotic notation ในการแสดง worst-case complexity
Asymptotic notation
ใน Asymptotic notation เค้าแบ่งย่อยออกไปได้เป็น Asymptotic function อีก 3 function คือ Big Θ (theta) และ Big Ω (omega) และ Big O notation ที่จะกล่าวต่อไปจะเป็นส่วนของ Big O notation เท่านั้น ใน Asymptotic notation นั้นก็ถือเป็นเครื่องหมายทางคณิตศาสตร์ที่จะอธิบายถึงลิมิตของพฤติกรรมของ Function ซึ่งถูกคิดค้นขึ้นโดย Paul Bachmann, Edmund Landau และคนอื่น ๆ โดยพวกเขาเรียกมันว่า Bachmann–Landau notation หรือ asymptotic notation นั่นเอง
จากที่ได้กล่าวไปข้างต้น Time Complexity คือความซับซ้อนของการคำนวณที่จะอธิบายระยะเวลาที่ใช้ในการเรียกใช้ Algorithm ส่วน Asymptotic notation (ส่วนของ Big O notation) เป็นการหาความซับซ้อนของระยะเวลา (time execution) ที่แย่ที่สุด (worst-case complexity)
ผมว่าอาจจะงงได้ ลองมาดูตัวอย่างการหา Big O notation กันครับ
สมมติว่าผมมี Array 26 ช่อง ใน Array เก็บตัวอักษร A–Z เอาไว้แบบเรียงกันหมด เราต้องการหาตัว F ถ้าจินตนาการก็คือ Array ช่องที่ 5 ถูกไหมครับ เราก็เขียนโปรแกรมเรียก Array ช่องที่ 5 ออกมาเลย เนื่องจากเรารู้อยู่แล้วว่า A-Z ตัว F คือตัวอักษรตัวที่ 6 แบบนี้เราจะได้ O(1) ซึ่งเป็นวิธีที่ไวมาก แต่ถ้าหากผมเปลี่ยนโจทย์ เป็น Array 26 ช่อง ใน Array เก็บตัวอักษร A-Z แบบไม่เรียงกัน คุณก็จะไม่ทราบว่าตัวอักษรที่ต้องการหานั้นอยู่ที่ช่องไหนของ Array คุณจำเป็นต้อง Loop เพื่อหาตัวอักษรที่ต้องการ ถ้าหากซวย เราอาจจะได้ Array ช่องที่สุดท้าย ใน Big O notation เราสนใจตรงความซวยตรงนี้แหละครับ ในกรณีตัวอย่างนี้เราจะได้ค่าเป็น O(n)
จากตัวอย่างทั้งสอง จะเห็นว่าแค่ตัวอักษรแค่ 26 ตัวแค่นี้ มันก็ไม่น่าจะมีผลเท่าไหร่ ก็จริงครับ แต่ในกรณีที่ไม่ใช่แค่ตัวอักษรหละ แต่เป็นการค้นหาข้อมูลที่อยู่ใน Array หลาย ๆ ล้านเรคคอร์ด การใช้ Big O notation แบบ O(n) จากตัวอย่างข้างบน worst-case complexity ของเราจะต้อง Loop หลาย ๆ ล้านรอบทำให้เสียเวลามากขึ้นตามปริมาณของข้อมูลที่เราใช้ค้นหา… ถ้าหากเรามีวิธีที่ดีกว่านี้หละ ถ้าหากเรามีวิธีที่ทำให้การค้นหาแย่ที่สุดจาก 1,000,000 รอบ เหลือ 500,000 รอบ หรือน้อยกว่านั้นได้หละ มันก็คงจะดีกว่าใช่ไหมหละครับ นี่แหละครับที่ทำให้ทุกคนควรสนใจกับ Time Complexity
Orders of common functions
Algorithmic complexities จะถูกจำแนกตามประเภทของ Function ใน Big O notation
ใน Wiki ของ Time complexities เค้าจำแนกไว้ 20 แบบ
ใน Wiki ของ Big O notation เค้าจำแนกไว้ 13 แบบ
ซึ่งตัวผู้เขียนเองก็ไม่ได้ใช้ทั้งหมด จะขอหยิบที่ได้เห็นบ่อย ๆ ขึ้นมาเป็นตัวอย่างนะครับ
Constant (O(1))
O(1) เป็นสิ่งที่เหล่าพัฒนาโปรแกรมน่าจะอยากเจอที่สุดแล้วครับ เนื่องจากไม่ว่าปริมาณของข้อมูลจะมากมายแค่ไหน ระยะเวลาในการประมวลผลก็จะใช้เพียงแค่ 1 รอบ
function findCharacterH(){
String[] characters = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};
print(characters[7]);
}จากตัวอย่าง เรารู้อยู่แล้วว่าตัวอักษร H อยู่ตรงไหน เราจึงหยิบข้อมูลนั้นมาใช้ได้ทันที
Logarithmic (O(log n))
O(log n) ตัวอย่าง Algorithm ทั่วไปของ O(log n) คือ Binary Search ซึ่งจะเป็นการค้นหาแบบค่อย ๆ แบ่งครึ่งไปเรื่อย ๆ ข้อดีของมันคือไวกว่า O(n) มากกก แต่ข้อเสียคือ ข้อมูลที่จะทำ Binary Search ต้องถูก Sort ก่อน
function main() {
int arr[] = { 2, 4, 6, 8, 11, 24, 36 };
int fine = 24;
int result = binarySearch(arr, 0, arr.length - 1, fine);
println("Result at index: " + result);
}function binarySearch(int arr[], int l, int r, int fine) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == fine) return mid;
if (arr[mid] > fine) return binarySearch(arr, l, mid - 1, fine);
return binarySearch(arr, mid + 1, r, fine);
}
return -1;
}
จากตัวอย่างเป็นตัวอย่างการทำ Binary Search โดยการหาตัวเลข 24 ซึ่งใช้รอบในการหาเพียง 2 รอบเท่านั้นเอง
Linear (O(n))
O(n) จะเป็น Algorithm ที่ใช้ระยะเวลาในการค้นหาตามปริมาณข้อมูลที่มี ที่แย่ที่สุดจะไม่เกินปริมาณของตัวเอง เช่นข้อมูลมี 26 ตัว การค้นหาก็จะแย่ที่สุดคือ 26 ครั้ง
function findCharacterH(){
String[] characters = {"C", "B", "D", "E", "F", "I", "J", "L", "M", "A", "N", "O", "P", "K", "Q", "R", "S", "T", "U", "G", "V", "W", "X", "Y", "Z", "H"};
for(int i = 0; i < characters.length; i++){
if(characters[i] == "H"){
print(characters[i]);
print(i);
}
}
}จากตัวอย่างเราได้ทำการสลับตัวอักษรที่อยู่ใน Array แล้วเราต้องการค้นหาตัว H แต่ตัว H ดันได้อยู่ด้านหลังสุด ทำให้เราจำเป็นต้อง Loop 26 รอบ
Linearithmic (O(n log n))
O(n log n) จะเป็น Algorithm ที่จะมีการใช้ซ้อน Loop โดยปกติถ้าซ้อน Loop ธรรมดา ค่าที่ได้มักจะเป็น O(n²) เนื่องจากจะเป็นการวนให้ครบให้หมด (worst-case complexity) แต่ในเมื่อเป็น O(n log n) ภายใน Loop ที่สองที่ซ้อนอยู่นั้น จะเป็นการทำ log n อีกที จึงทำให้วิธีนี้ไม่ใช้พลังงานอย่าง O(n²) เราจะพบ O(n log n) ได้จาก Merge Sort, Heap Sort หรือ Quick Sort
for (int i = 1; i <= 8; i++){
for(int j = 1; j < 8; j = j * 2) {
println("I: " + i + " J: " + j);
}
}จากตัวอย่าง ถ้าลองนำ Code ไปรันจะเห็นว่า O(n log n) = O(8 log(8)) ได้ทั้งหมด มีวนทั้งหมด 24 รอบ
Quadratic (O(n²))
O(n²) จะเป็น Algorithm ที่ถือเป็น 2-nested loop ก็คือการซ้อน Loop นั่นเอง เราจะพบ O(n²) ได้จาก Bubble Sort, Insertion Sort, Selection Sort หรือในทีมของคุณเองก็น่าจะเจอครับ ฮ่า ๆ วิธีแก้บางทีมันติดอยู่ที่ปลายจมูก จาก O(n²) อาจจะเหลือ O(n log n) ก็ได้ใครจะไปรู้
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
println("I: " + i + " J: " + j);
}
}จากตัวอย่างจะเห็นว่า ถ้าค่า n เป็น 10 จะต้องทำการวนทั้งหมด 100 รอบ ดูไม่เยอะมาก แต่ถ้าค่า n เป็น 100 เราจะต้องวนทั้งหมด 10,000 รอบ!!!
Cubic (O(n³))
O(n³) จะเป็น Algorithm ที่ถือเป็น 3-nested loop คือการ Loop ซ้อน Loop แล้วก็ซ้อน Loop อีกที ตัวนี้มีความช้ามาก มากกว่า O(n²) ยิ่งดาต้าเยอะ ยิ่งทวีคูณเข้าไปอีก เอาง่าย ๆ ว่ายิ่งเลขยกกำลังเยอะ ยิ่งแย่
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
println("I: " + i + " J: " + j + " K: " + k);
}
}
}จากตัวอย่างจะเห็นว่า ถ้าค่า n เป็น 10 จะต้องทำการวนทั้งหมด 1,000 รอบ นี่แค่ n เป็น 10 ยังใช้ 1,000 รอบ แล้วถ้าค่า n เป็น 100 เราจะต้องวนทั้งหมด กี่รอบ!!!
Exponential (O(2^n))
O(2^n) จะเป็น Algorithm ที่อย่าได้พบเจอกันดีกว่า ชื่อมันก็บอกอยู่แล้วครับว่า Exponential แค่ n = 4 ก็จัดไป 16 รอบแล้ว ปรับเป็น n = 16 ใช้ไป 256 รอบ
for (int i = 1; i <= Math.pow(2, n); i++){
print("round: " + i);
}จากตัวอย่างถ้าให้ค่า n เป็น 1,024 จะต้องใช้ทั้งหมด 2¹⁰²⁴ รอบ
Factorial (O(n!))
O(n!) การทำงานของ Algorithm แบบ O(n!) จะใช้เวลาทำงานเพิ่มขึ้นเป็นแบบ Factorial ตามสัดส่วนที่ Input เข้ามาเลยเลย Classic case ที่เขามายกตัวอย่างกันผมเจอก็จะเป็น Travelling salsman problem ไม่ว่าจะ Research เว็บไหนก็มักจะเจอเคสนี้ แล้วก็ใช้ brute-force ในการแก้ปัญหา
มาดูตัวอย่าง Factorial กันสักเล็กน้อย
n > 0 n! = 1 x 2 x 3 x 4 x … x n
n = 0 0! = 1
function factorial(int n) {
double f = 1.0;
for (int k = 2; k <= n; k++) {
f = f * k;
}
return f;
}แค่ n มีค่าเป็น 8 ก็ใช้ไป 40,320 รอบแล้ว
How to find Big O
Assume the worst
การคำนวณหาค่า Big O ให้คิดถึงกรณีที่แย่ที่สุดเสมอ ตัวอย่างเช่นหากต้องการวนซ้ำใน Array และค้นหาข้อมูลบางอย่าง เราอาจจะเจอตั้งแต่รอบแรก หรือรอบสุดท้าย ให้ถือว่าเราต้องคิด Big O เป็นรอบที่แย่ที่สุด จะได้ O(n) นั่นเอง
Remove constants
ในกรณีที่การทำงานของ Function เรามีทั้ง O(1) และ O(N) เราสามารถตัด O(1) ได้ เนื่องจากตามกฎทั่วไปแล้ว มันไม่มีนัยยะสำคัญ เมื่อเทียบกับ O(n) ใน Function ของเรา ต่อให้ ใน Array ของเรามีข้อมูล 1,000,000 เรคอร์ด O(1) ก็ไม่มีผลอะไร
Use different terms for inputs
หากเราต้องการวนรอบ 2 เท่า ของ Array เดียวกัน Big O ของเราจะเป็น O(2n) แต่ก็ให้คิดแบบ Remove constants ข้อ 2 ดังนั้นจะเหลือแค่ O(n) เนื่องจาก input เดียวกัน ไม่มีผลต่อ Big O
ถ้าหากมี input เข้ามาใน Function พร้อมกันแต่ต่างกันเรื่องข้อมูล เช่น Function a รับ parameter n และ m แล้วนำมาแยก Loop กัน คนละ Loop จะได้ O(m + n) อยากให้ลองพิจารณาตัวอย่างจาก Code ด้านล่างจะได้เห็นภาพมากขึ้น
function a(int n, int m){
for(n){}
for(m){}
}ถ้าหาก Function a รับ parameter n และ m แล้วนำมาทำ Loop ซ้อน Loop จะได้ O(n * m) ลองพิจารณาจากตัวอย่าง Code ด้านล่าง
function a(int n, int m){
for(n){
for(m){}
}
}ถ้าหาก Function a รับ parameter n แล้วนำมาทำ Loop ซ้อน Loop (2-nested loop) จะได้ O(n²) ซึ่งเป็นสิ่งที่เราควรจะ Refactor code ในส่วนนี้ เนื่องจากการทำ Loop ซ้อน Loop ทำให้จำนวนการวนรอบในการหานั้นทีวีคูณ ลองพิจารณาจากตัวอย่าง Code ด้านล่าง
function a(int n){
for(n){
for(n){}
}
}Drop any non dominants
ให้ลองพิจารณาจาก Code ด้านล่าง จะเห็นว่าเรามี O(n) และ O(n²) ดังนั้น Big O ทั้งหมดของเราจะได้เป็น O(n + n²) แต่อย่างที่เราได้เรียนรู้ไปในกฎข้อที่ 2 Remove constants ดังนั้นเราควรปล่อย O(n) และเก็บเป็น O(n²) เนื่องจากเป็นสิ่งที่สำคัญกว่า และมันเป็นค่าที่มีผลกระทบต่อประสิทธิภาพการทำงานมากกว่า
function a(int[] n){
for(int ns: n){
print ns
} for(int i: n){
for(int j: n){
print i, j
}
}
}
Conclusion
Big O notation อาจจะดูมีประโยชน์ไม่มากนักกับ Algorithm ที่มี Input ขนาดเล็ก แต่มันจะมีประโยชน์มากกับ Input ขนาดใหญ่ เราควรเลี่ยง O(2^n), O(n!), O(n²), O(n³) ถ้าเป็นไปได้ สิ่งที่ควรทราบอีกอย่างนึงเกี่ยวกับ Asymptotic notation นอกจาก Big O แล้ว ใน Asymptotic function มันยังมี Big Θ (theta) และ Big Ω (omega) อยู่อีกด้วย
ก็จบไปแล้วนะครับสำหรับเรื่อง Big O notation ที่จริงยังมีอีกหลายตัวที่ไม่ได้กล่าวถึง รวมถึงที่ได้กล่าวถึงก็ไม่ได้ลงดีเทลลึก ๆ ลงไปเนื่องจากมันมีรายละเอียดปลีกย่อยเยอะ ก็หวังว่าผู้อ่านทุกท่านจะได้ทบทวนความรู้ และเข้าใจ Complexity ของ Algorithm ที่สามารถส่งผลกระทบต่อเวลาการทำงานของเราได้กันไม่มากก็น้อย แล้วผมก็หวังว่าผู้อ่านทุกท่านจะได้นำข้อมูลเรื่องนี้ไปใช้วิเคราะห์กันก่อนที่จะลงมือเขียนโปรแกรม
อย่าลืมนะครับการพัฒนาซอฟแวร์ ไม่ใช่สักแต่ว่าทำให้มันรันได้ ควรจะทำให้มันมีคุณภาพด้วย
