คู่มือเริ่มต้นสำหรับสัญกรณ์ Big O

Big O Notation เป็นวิธีแสดงว่าอัลกอริทึมจะใช้เวลาดำเนินการนานเพียงใด ช่วยให้วิศวกรซอฟต์แวร์สามารถกำหนดวิธีการต่างๆในการแก้ปัญหาได้อย่างมีประสิทธิภาพ

ความซับซ้อนของเวลาทั่วไปบางประเภทในสัญลักษณ์ Big O มีดังนี้

  • O (1) - ความซับซ้อนของเวลาคงที่
  • O (n) - ความซับซ้อนของเวลาเชิงเส้น
  • O (log n) - ความซับซ้อนของเวลาลอการิทึม
  • O (n ^ 2) - ความซับซ้อนของเวลากำลังสอง

หวังว่าในตอนท้ายของบทความนี้คุณจะสามารถเข้าใจพื้นฐานของ Big O Notation

O (1) - เวลาคงที่

อัลกอริทึมเวลาคงที่จะใช้เวลาในการดำเนินการเท่ากันเสมอ เวลาดำเนินการของอัลกอริทึมเหล่านี้ไม่ขึ้นอยู่กับขนาดของอินพุต ตัวอย่างที่ดีของ O (1) เวลาคือการเข้าถึงค่าด้วยดัชนีอาร์เรย์

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

ตัวอย่างอื่น ๆ ได้แก่ การดำเนินการ push () และ pop () บนอาร์เรย์

O (n) - ความซับซ้อนของเวลาเชิงเส้น

อัลกอริทึมที่มีความซับซ้อนเส้นเวลาถ้ามีเวลาในการดำเนินการขั้นตอนวิธีเป็นสัดส่วนโดยตรงกับขนาดการป้อนข้อมูลn ดังนั้นเวลาที่ใช้ในการรันอัลกอริทึมจะเพิ่มขึ้นตามสัดส่วนเมื่อขนาดของอินพุตnเพิ่มขึ้น

ตัวอย่างที่ดีคือการค้นหาซีดีในกองซีดีหรืออ่านหนังสือโดยที่ n คือจำนวนหน้า

ตัวอย่างใน O (n) ใช้การค้นหาเชิงเส้น:

//if we used for loop to print out the values of the arrays
for (var i = 0; i < array.length; i++) { console.log(array[i]);}
var arr1 = [orange, apple, banana, lemon]; //=> 4 steps
var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O (log n) - ความซับซ้อนของเวลาลอการิทึม

อัลกอริทึมที่มีความซับซ้อนเวลาลอการิทึมถ้าเวลาที่ใช้ในการเรียกใช้อัลกอริทึมเป็นสัดส่วนกับลอการิทึมของขนาดการป้อนข้อมูลที่n ตัวอย่างคือการค้นหาแบบไบนารีซึ่งมักใช้เพื่อค้นหาชุดข้อมูล:

//Binary search implementationvar doSearch = function(array, targetValue) { var minIndex = 0; var maxIndex = array.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = array[currentIndex]; if (currentElement  targetValue) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; //If the index of the element is not found.};
var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];
doSearch(numbers, 23) //=>; 6

ตัวอย่างอื่น ๆ ของความซับซ้อนของเวลาลอการิทึม ได้แก่ :

Example 1;
for (var i = 1; i < n; i = i * 2) console.log(i);}
Example 2;
for (i = n; i >= 1; i = i/2) console.log(i);}

O (n ^ 2) - ความซับซ้อนของเวลากำลังสอง

อัลกอริทึมมีความซับซ้อนของเวลากำลังสองหากเวลาในการดำเนินการนั้นเป็นสัดส่วนกับกำลังสองของขนาดอินพุต ตัวอย่างที่ดีคือการตรวจสอบว่ามีรายการที่ซ้ำกันในสำรับไพ่หรือไม่

คุณจะพบกับความซับซ้อนของเวลากำลังสองในอัลกอริทึมที่เกี่ยวข้องกับการวนซ้ำแบบซ้อนกันเช่นซ้อนกันสำหรับลูป ในความเป็นจริงลูปที่ซ้อนกันลึกจะส่งผลให้เกิดO (n ^ 3), O (n ^ 4) เป็นต้น

for(var i = 0; i < length; i++) { //has O(n) time complexity for(var j = 0; j < length; j++) { //has O(n^2) time complexity // More loops? }}

ตัวอย่างอื่น ๆ ของความซับซ้อนของเวลากำลังสอง ได้แก่ การเรียงฟองการเรียงลำดับการเลือกและการเรียงลำดับการแทรก

บทความนี้ใช้เฉพาะรอยขีดข่วนบนพื้นผิวของสัญลักษณ์ Big O เท่านั้น หากคุณต้องการทำความเข้าใจเพิ่มเติมเกี่ยวกับ Big O Notation ขอแนะนำให้ตรวจสอบ Big-O Cheat Sheet