Big O notation
การจะเปรียบเทียบ algorithm ต่างๆ ว่ามีความเร็ว-ช้าต่างกันอย่างไรนั้นอาจทำได้ด้วยการรันแล้วจับเวลา (benchmark) แต่ผลลัพท์ที่ได้นั้นก็จะมีข้อเสียอยู่หลายอย่าง เช่น
- เครื่องคนละเครื่องกันทำงานได้เร็วไม่เท่ากัน
- การจัดสภาพแวดล้อมขณะทดสอบ (เช่นเทส algorithm a ตอน cpu ว่าง แล้วไป test algorithm b ตอน cpu 100%)
- optimization ต่างกัน (compiler จะปรับปรุงโค้ดเราอัตโนมัติให้ทำงานไวขึ้น ซึ่งกระบวนการเหล่านี้อยู่นอกเหนือจากการควบคุมของเรา และ compiler คนละตัวอาจจะให้ผลลัพท์ต่างกัน)
วิธีที่เป็นมาตรฐานในวงการในการเปรียบเทียบสมรรถนะของอัลกอริธึมนั้นจะใช้สัญกรณ์ Big O (Big O notation) ในการระบุถึงเวลาที่อัลกอริธึมใช้เมื่อเทียบกับขนาดข้อมูลรับเข้า (Time complexity)
สมบัติ
- สัมพัทธ์: ไม่สามารถใช้ Big O เปรียบเทียบอัลกอริธึมคนละประเภทกันได้ เช่นไม่สามารถเทียบความเร็ว sorting algorithm กับ search algorithm ได้
- เป็นตัวแทน: Big O ทำให้สามารถเปรียบเทียบได้ง่ายจากการที่ติดตัวแปรไว้แค่ตัวเดียวคือ n หรือขนาดข้อมูลรับเข้า และฟังก์ชั่นที่ใช้ทำกับตัวแปรนั้นก็มาจากการสังเกตจุดที่มีนัยสำคัญที่สุดในอัลกอริธึมนั้นๆ ว่าทำกี่ครั้ง (เช่นปกติแล้วการเขียน Big O ของ sorting algorithm จะดูจากว่ามีการเปรียบเทียบกี่ครั้ง แต่ถ้าสมมุติว่าการสลับที่สมาชิกกันใช้เวลามากกว่าการเปรียบเทียบ ก็ต้องมาหา Big O ใหม่ที่คำนวณจากจำนวนครั้งในการสลับที่)
- บอกความซับซ้อน: Big O เป็นตัวบอกว่าเวลาที่ใช้ประมวลผลข้อมูลนั้นแปรผันอย่างไรจากขนาดของข้อมูล
ตัวอย่าง
การบวก
- ถ้าต้องการหาค่าของ 1+2+3 ต้องบวกทั้งหมด 2 ครั้ง
- ถ้าต้องการหาค่าของ 1+2+3+4 ต้องบวกทั้งหมด 3 ครั้ง
- ถ้าต้องการหาค่าของ 1+2+3+4+5 ต้องบวกทั้งหมด 4 ครั้ง
จะเห็นว่าจำนวนครั้งที่ใช้คือ n-1 ครั้ง โดย n คือจำนวนตัวเลขที่เอามาบวกกัน ฉะนั้นแล้วจะเขียนได้ว่าการบวกเป็น O(n)
ข้อสังเกตคือเราไม่เอา -1 มาเขียนด้วย เพราะเมื่อ n เป็นเลขที่มีค่ามากๆ แล้ว -1 นั้นแทบจะไม่มีนัยสำคัญเหลือเลย
อัลกอริธึมที่มีความเร็ว O(n) นั้นเรียกว่า linear complexity
การคูณ
1234 x
1234
-------
4936
37020
246800
1234000
-------
1522756
การคูณเลขด้วยมือนั้นวิธีการทำคือเอาแต่ละหลักของตัวล่างคูณแต่ละหลักของตัวบน เช่น 1234x1234 จะต้องทำ 1234x4, 1234x3, 1234x2, 1234x1 หรือแตกย่อยไปอีกคือ 1x4, 2x4, 3x4, 4x4, 1x3, 2x3, 3x3, .... ฉะนั้นแล้วจะพบว่าจำนวนครั้งที่ต้องคูณคือ a*b ครั้ง โดย a, b คือความยาวของเลขแต่ละตัว
เมื่อคูณเสร็จแล้วยังจะต้องเอาผลลัพท์ที่ได้เข้ามาบวกอีก ซึ่งอาจจะต้องบวกถึง 2n หลัก
จะเห็นว่าอาจจะเขียนได้ว่า O(n^2 + 2n) แต่ในกรณีนี้เราจะถือว่าการบวกที่เป็นแค่ O(2n) นั้นแทบไม่มีนัยสำคัญเลยเพราะการคูณใช้จำนวนครั้งมากกว่า เราจึงสรุปได้ว่าการคูณเป็น O(n^2)
(ทั้งนี้ไม่สามารถเอา Big O ของการคูณและการบวกไปเทียบกันได้เพราะเป็นคนละประเภทกัน)
ข้อสังเกตคือในการบวก จากตัวอย่างจะเห็นว่า 1234x1234 นั้นบวกกันแค่ 7 หลัก น้อยกว่า 2n = 8 หลัก เพราะการเขียน Big O โดยทั่วไปถ้าไม่ระบุจะคิดถึงกรณีที่ช้าที่สุดไว้เสมอคือคูณแล้วได้คำตอบออกมา 8 หลัก
อัลกอริธึมที่มีความเร็วเป็น O(n^2) มีชื่อเรียกว่า quadratic complexity
สมุดโทรศัพท์
การเปิดสมุดโทรศัพท์ซึ่งมีรายชื่อเรียงตามตัวอักษรนั้น วิธีที่สิ้นคิดที่สุดคือเปิดไล่ไปเรื่อยๆ วิธีนี้ถ้าต้องการหาชื่อคนสุดท้ายต้องเปิดไล่ไปจนครบทุกคน ฉะนั้นจะใช้เวลาทำงาน O(n)
วิธ๊ที่เร็วกว่านั้นทำได้ด้วยการใช้ binary search ซึ่งเป็นอัลกอริธึมแบบ divide and conquer แบบหนึ่ง วิธีการคือ
- เปิดไปที่กลางเล่ม
- อ่านชื่อแล้วดูว่าชื่ออยู่ก่อนหรือหลังคนที่เราตามหา
- ถ้าอยู่ก่อน เปิดไปครึ่งของครึ่งเล่มด้านหน้า ถ้าอยู่หลังก็ทำคล้ายๆ กัน
- ทำไปเรื่อยๆ จนกว่าจะเจอ
กรณีนี้จะเห็นว่า
- มี 3 ชื่อต้องอ่านชื่อ 2 ครั้ง (ชื่อคนกลาง แล้วถ้าไม่ใช่คนที่ตามหา ก็ต้องอ่านชื่อคนแรก ไม่ก็คนหลัง)
- มี 7 ชื่อ อ่าน 3 ครั้ง
- มี 15 ชื่อ อ่าน 4 ครั้ง
- มี 1 ล้านชื่อ อ่าน 20 ครั้ง
จากเดิมที่เปิดไล่ตรงๆ ต้องอ่าน 1 ล้านครั้งเหลือแค่ 20 ครั้ง เรียกได้ว่าเร็วกว่ากันหลายเท่าตัวทีเดียว
อัลกอริธึมประเภท divide and conquer นี้มักจะมีความซับซ้อนแบบ O(log n) หรือเรียกว่า logarithmic complexity
กรณีที่เกิดขึ้นได้กับอัลกอริธึม
บางครั้ง Big O ยังใช้กล่าวถึงกรณีอื่นๆ นอกจากกรณีที่ช้าที่สุดของ algorithm ได้อีกด้วย เช่นในการเปิดสมุดโทรศัพท์นี้
- กรณีดีที่สุด: O(1) หรือเรียกว่า constant complexity นั่นคือเปิดปุ๊บเจอเลย
- กรณีทั่วไป: O(log n)
- กรณีช้าสุด: O(log n)
Traveling salesman
ปัญหา Traveling salesman เป็นปัญหาคลาสสิกเรื่องหนึ่ง
ถ้ามีเมืองอยู่ n เมืองโดยทราบระยะทางระหว่างแต่ละเมือง อยากทราบว่าจะเดินทางอย่างไรให้ไปครบทุกเมืองโดยสั้นที่สุดโดยไม่ซ้ำเมืองเดิม และกลับมาที่จุดเริ่มต้น
กรณีนี้จะเห็นว่ากรณีที่เป็นไปได้ทั้งหมดนั้นมี n! กรณี ฉะนั้นแล้วอัลกอริธึมพื้นฐานในการแก้ปัญหานี้จึงเป็น O(n!) หรือเรียกว่า factorial/combinatorial complexity
กรณีอื่นๆ
- O(1): การเข้าอ่านสมาชิกใน array (เรียกตัวไหนก็อ่านได้ไวเท่ากัน)
- O(n log n): Heapsort (การเรียงข้อมูลที่กล่าวถึงใน lecture 2)
- O(2^n): Fibbonacci (f(x) = f(x-1) + f(x-2))
ตัวอย่างด้วยโค้ด
O(1)
for(int i = 0; i < 10; i++){
a[i] = 5;
}
O(n)
for(int i = 0; i < n; i++){
a[i] = 5;
}
O(n^2)
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
a[i] = 5;
}
}