Big O Notation กาลเวลาและพื้นฐานที่ต้องรู้ !!
สวัสดีทุกๆท่านที่เข้ามาอ่านทุกท่านนะครับ ห่างหายกันไปนานมากกับการเขียนบทความของผม วันนี้ผมจึงอยากจะพาทุกคนมาทบทวนเรื่อง Big O Notation ที่ทุกคนอาจจะทราบกันดีอยู่แล้ว หรือ บางท่านอาจจะลืมไปแล้วบ้าง วันนี้เราจะมาทบทวนกันว่า Big O นั้น จะช่วยลดทรัพยากรในการประมวลผล และ ระยะเวลาในการทำงานได้ยังไงกัน
Big O Notation คือ
ระยะเวลาในการประมวลผลที่แย่ที่สุด (worst-case complexity) หรือ ใช้พื้นที่และทรัพยากรมากที่สุดในการ compile อัลกอริทึมใดๆ หรือที่เรียกกันว่า ความซับซ้อนของอัลกอริทึม (Algorithm Complexity)
ประเภทของ Big O Notation
เราจะแทน Big O Notation ด้วย O(n) ซึ่ง n ในที่นี้จะแทนด้วยจำนวนของข้อมูลหรือขนาดข้อมูลที่จะนำไปประมวลผลด้วยอัลกอริทึมของเรา ถ้าลองศึกษาจริงๆ ประเภทของ Big O Notation นั้นมีเยอะมาก ดังนั้นผมจะขอยกประเภทหลักๆที่เราเห็นหรือใช้งานง่ายๆ มา 6 ประเภท ด้วยกัน โดยเราจะดูผลลัพธ์กันที่ case และ ระยะเวลาการทำงานเป็นหลักครับ
1.O(1) Constant
เรียกได้ว่าเป็นอัลกอริทึมที่ดีที่สุด เพราะไม่ว่าจะใส่ Input ไปเท่าใด หรือ มากขนาดไหน ระยะเวลาประมวลผลก็จะอยู่ที่ 1 ครั้งเสมอ ลองดูได้จากตัวอย่างด้านล่าง
fun isModZero(num: Int): Boolean {
return num % 2 == 0
}2.O(log n) Logarithmic
เป็นอัลกอริทึมที่อยู่ในระดับดีเยี่ยม โดยที่การทำงานของอัลกอริทึมนี้จะลดจำนวนลูปครึ่งนึงทุกครั้งที่มีการทำงานสำเร็จ หรือที่เราใช้กันบ่อย ก็คือ Binary Search เป็นการค้นหาตำแหน่งของตัวเลข array ที่มีการ Sort ไว้แล้ว
val arr = listOf(1, 2, 3, 5, 8, 13, 21)
val fine = 8fun binarySearch(arr: List<Int>, fine: Int, first: Int, last: Int): Int {
return if (last >= first) {
val mid = first + (last - first) / 2
when {
arr[mid] == fine -> {
mid
}
arr[mid] > fine -> {
binarySearch(arr, fine, first, mid - 1)
}
else -> {
binarySearch(arr, fine, mid + 1, last)
}
}
} else {
-1
}
}
3.O(n) Linear
เป็นอัลกอริทึมที่มีการทำงานอยู่ในระดับที่ดี การทำงานของอัลกอริทึมนี้จะทำงานตามจำนวน Input ที่ใส่เข้ามา ใน case ที่แย่ที่สุด จะทำงานไม่เกิน input ที่ใส่เข้ามา ยิ่งถ้า input มีจำนวนที่เยอะ การทำงานก็จะเยอะตามไปด้วย
val arr = listOf(1, 2, 3, 5, 8, 13, 21)
val fine = 8fun linearSearchNumber(arr: List<Int>, fine: Int): Int {
for (i in arr) {
if (i == fine) return i
}
return -1
}
4.O(n log n) Linearithmic
อัลกอริทึมนี้จะอยู่ในระดับกลางๆ เป็นการทำงานแบบซ้อนลูป ในทำงานจะมีการวนลูปแบบ O(n) ที่มีการทำงานลูป O(log n) ที่ตัดข้อมูลที่ไม่ได้ใช้งานออกทีละครึ่ง อยู่ข้างในอีกที จากตัวอย่างด้านล่าง เป็นตัวอย่างแบบสั้นๆ ครับ
fun linearithmicSearch() {
for (i in 1..13) {
var j = 1
while (j < 13) {
println("I: $i J: $j")
j *= 2
}
}
}5. O(n²) Quadratic
อัลกอริทึมนี้จะอยู่ในระดับกลาง ที่ต่อมาจาก O(n log n) แต่ว่าเริ่มที่จะไม่ดีแล้ว โดยการทำงานของ O(n²) จะเป็นการซ้อนลูปที่ยิ่งจำนวน n เยอะ การทำงานก็จะเยอะตามไปด้วยนั่นเอง
fun quadraticSearch() {
for (i in 1..4) {
for (j in 1..4) {
println("I: $i J: $j")
}
}
}6. O(n!) Factorial
เป็นประเภทสุดท้ายที่จะหยิบมาพูดถึง อัลกอริทึมประเภทนี้อยู่ในวิกฤตมากๆ แล้ว ยิ่ง n มากขึ้น การทำงานก็จะมากขึ้นด้วย ตามสัดส่วนของ Factorial
fun factorial(num: Int): Int {
if (num == 1) return 1
for (i in 0..num)
return num * factorial(num - 1)
return -1
}มีกราฟมาให้ดูคราวๆ กันว่า Big O ในแต่ละแบบถึงระยะเวลาประมวลผล เมื่อมีจำนวน Input ที่มากขึ้นครับ
สรุป
ก็เป็นการรื้อฟื้นพื้นฐานที่จำเป็นต้องรู้กันถ้าเราเป็น developer ว่า Big O Notation นั้นมีความสำคัญขนาดไหน ในบ้างอัลกอริทึมที่เราคาดไม่ถึงอาจจะมีผลร้ายกับงานของเราก็เป็นได้ ทั้งนี้จริงๆ ใน Big o Notation ยังมีอีกหลายประเภทมาก ถ้าอยากจะอ่านต่อดูได้จากลิ้งค์ด้าน
