Data Structure & Algorithm(EP.6) — การคำนวณ Big-O

ขั้นตอนการคำนวณ Big-O

1. หา Worst Case และ Constant
2. ลบส่วนที่เป็น Constant (ค่าคงที่ เช่น ตัวเลข)
3. แยกเคส Big — O ออกเป็นส่วนๆและลดรูปฟังก์ชั่น

1. หา Worst Case และ Constant พิจารณาขั้นตอนการดำเนินการของอัลกอริทึม
   ซึ่งแต่ละขั้นตอนจะนับการทำงานเป็น 1 ครั้ง เช่น ถ้าคำสั่งมี if, switch หรือ ตัวดำเนินการ +, -, >, <,= ให้ถือว่าเป็น Constant

let count = 0 //1
let total = (1+n) * (n/2) //1

ผลรวมของฟังก์ชั่น f(n) = 1+1 = 2 หรือ O(2)
เขียนลดรูป O(2) → O(1)

2. ลบส่วนที่เป็น Constant

function summation(n){
    total=0 //O(1)
    for(i=0;i<n;i++){ // O(n)
       total+=i //ทำงาน n ครั้ง
    }
   return total //O(1)
}

f(n) = 1+n+1 = 2+n หรือ O(2+n) → O(n)

3. แยกเคส Big — O ออกเป็นส่วนๆและลดรูปฟังก์ชั่น
3.1 ถ้าใช้งานลูปอยู่ในระดับเดียวกัน ให้นำ Big O มาบวกกัน

โครงสร้าง : O(m + n)

//ตัวอย่างที่ 1
function allItems(array1,array2){
    for (let i = 0; i < array1.length; i++) { //O(n)
        console.log(array1[i])
    }
    for (let j = 0; j < array2.length; j++) { //O(n)
        console.log(array2[j])
    }
}

O(n)+O(n) = O(2n)
เขียนลดรูป = O(n)

//ตัวอย่างที่ 2
function items(array1,size){
    console.log(array1[0]) //O(1)
    for (let i = 0; i < size/2; i++) { //O(n/2)
        console.log(array1[i])
    }
    for (let j = 0; j < 100; j++) { //O(100)
         console.log(j)
    }
}

O(1)+O(n/2)+O(100)
O(1+n/2+100) เขียนลดรูป = O(n)

3.2 ถ้าใช้งาน Loop ซ้อนกันให้นำ Big O มาคูณกัน

โครงสร้าง : O(m x n)

function allItems(array1,array2){
    for(let i = 0; i < array1.length; i++){ //O(n) 
        console.log(`${array1[i]}`)
    }
    for (let i = 0; i < array2.length; i++) { //O(n)
        for (let j = 0; j < array2[i].length; j++) { //O(n)
            console.log(`${array2[i][j]}`)
        }
    }
}

O(n) + O(n) x O(n) = O(n+n²)
เขียนลดรูป = O(n²)

บทความที่เกี่ยวข้อง

• EP.1 — รู้จักกับโครงสร้างข้อมูลและอัลกอริทึม
• EP.2 — การวัดประสิทธิภาพอัลกอริทึม
• EP.3 — อัตราการเติบโตของฟังก์ชั่น
• EP.4 — การวิเคราะห์อัลกอริทึม
• EP.5 — Big-O Notation
• EP.6 — การคำนวณ Big-O
• EP.7 — ลิงค์ลิสต์ (Linked-List)
• EP.8 — สแต็ก (Stack)
• EP.9 — คิว(Queue)
• EP.10 — ทรี (Tree)
• EP.11 — Binary Search Tree (BST)
• EP.12 — กราฟ(Graphs)

เนื้อหาที่เกี่ยวข้อง

ช่องทางการสนับสนุน
🎓 คอร์สพัฒนาเว็บด้วย JavaScript 40 Workshop

🌎 ติดตามข่าวสารเพิ่มเติมได้ที่
Facebook | YouTube | TikTok