อะไรคือ Big-O Notation

คำเตือน: บทความนี้อาจไม่ถูกต้อง 100% หากอ่านแล้วคิดว่าไม่ถูกต้องตรงไหนสามารถแสดงความคิดเห็นได้นะครับ

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

สิ่งหนึ่งที่จะทำให้รู้ว่า Algorithm ทำงานได้มีประสิทธิภาพเรามักจะเห็นสัญลักษณ์ 𝑂(𝑔(𝑥)) เราจะมาอธิบายว่าสัญลักษณ์ที่ว่าข้างต้นเป็นอย่างไร โดยเน้นไปที่กระบวนการและการให้เหตุผลเป็นหลัก

Time Complexity

คือความซับซ้อนที่อธิบายถึงระยะเวลาในการเรียกใช้อัลกอริทึมเมื่อเทียบกับจำนวน Input เข้าไป สมมติว่ามีสมาชิกใน Array ทั้งหมด n ตัว และจำนวนครั้งที่ Algorithm ทำงานได้ทั้งหมด 2𝑛 + 3 ครั้ง เราก็จะได้จำนวนครั้งทั้งหมดโดยถูกเขียนเป็น 𝑇(𝑛) ซึ่ง 𝑛 คือจำนวนสมาชิกทั้งหมดใน Array จึงได้เป็น 𝑇(𝑛) = 2𝑛 + 3

(ต่อไปนี้เราจะเรียกจำนวนครั้งทั้งหมดที่ Algorithm รันได้คือ 𝑇(𝑛) )

Time Complexity นั้นก็จะมาประมาณค่าของ 𝑇(𝑛) ซึ่งจะเป็นในรูปแบบของการเติบโตของฟังก์ชั่นนั้น ตัวอย่างเช่น ถ้าเรามีการทำงาน 𝑇(𝑛) = 2𝑛 + 3 เราก็จะดูลักษณะของการเติบโตเมื่อ 0 ≤ 𝑛 ≤ 𝑘 เมื่อ 𝑘 ∈ 𝑍 และ 𝑘 ≥ 𝑛 แล้ว 𝑇(𝑘 + 1) > 𝑇(𝑘) โดย 𝑘 ≥ 𝑛 จะได้ Graph ในลักษณะ Linear เราสามารถที่จะเขียน Time Complexity ในลักษณะของ Asymptotic Notation

Asymptotic Notation

คือ สัญกรณ์ทางคณิตศาสตร์ (Mathematical Notations) ซึ่งใช้ในการอธิบายถึงจำนวนครั้งที่ทำงานโดยอัลกอริทึม ซึ่งจะมีอยู่ทั้งหมด 3 แบบคือ

Omega Notation (Ω-notation) คือเซทของการทำงานที่เร็วที่สุดของ Algorithm ซึ่งสามารถเขียนเป็น Ω(𝑔(𝑥)) เมื่อ 𝑥 คือจำนวน array ทั้งหมดซึ่ง 𝑥 ∈ 𝑍 โดย 𝑥 > 0 และ 𝑐 คือสัมประสิทธิ์ของ 𝑔(𝑥) ซึ่ง 𝑐 ∈ 𝑍 โดย 𝑐 > 0 และ 𝑔(𝑥) คือฟังก์ชันของการประมาณจำนวนครั้งที่ทำงานที่น้อยที่สุดและ 𝑓(𝑥) ∈ Ω(𝑔(𝑥)) แล้ว 0 ≤ 𝑐𝑔(𝑥) ≤ 𝑓(𝑥)

Theta Notation (Θ-notation) คือเซทของการทำงานที่ที่อยู่ตรงกลางระหว่าง 𝑐₁𝑔(𝑥) และ 𝑐₂𝑔(𝑥) ซึ่งใช้ในการหา Average Case (ถ้าสมมติว่าหา Average Case ไม่ได้ เราก็จะใช้ 𝑔(𝑥) ที่เหมือนกับ Big-O Notation แทน) สามารถเขียนเป็น (𝑔(𝑥)) เมื่อ 𝑥 คือจำนวน array ทั้งหมดซึ่ง 𝑥 ∈ 𝑍 โดย 𝑥 > 0 และ 𝑐₁, 𝑐₂ คือสัมประสิทธิ์ของ 𝑔(𝑥) ซึ่ง 𝑐₁, 𝑐₂ ∈ 𝑍 โดย 𝑐₁, 𝑐₂> 0 และ 𝑔(𝑥) คือฟังก์ชันของการประมาณจำนวนครั้งที่ทำงานที่เป็น Average และ 𝑓(𝑥) ∈ Θ(𝑔(𝑥)) แล้ว 0 ≤ 𝑐₁𝑔(𝑥) ≤ 𝑓(𝑥) ≤ 𝑐₂𝑔(𝑥)

Big-O Notation (O-notation) คือเซทของการทำงานที่ช้าที่สุดหรือแย่ที่สุดของ Algorithm ซึ่งสามารถเขียนเป็น 𝑂(𝑔(𝑥)) เมื่อ 𝑥 คือจำนวน array ทั้งหมดซึ่ง 𝑥 ∈ 𝑍 โดย 𝑥 > 0 และ 𝑐 คือสัมประสิทธิ์ของ 𝑔(𝑥) ซึ่ง 𝑐 ∈ 𝑍 โดย 𝑐 > 0 และ 𝑔(𝑥) คือฟังก์ชันของการประมาณจำนวนครั้งที่ทำงานที่เยอะที่สุดและ 𝑓(𝑥) ∈ 𝑂(𝑔(𝑥)) แล้ว 0 ≤ 𝑓(𝑥) ≤ 𝑐𝑔(𝑥)

เราอาจจะยังไม่ค่อยเห็นภาพกันใช่ไหมละครับ เพราะว่าผมก็งงเหมือนกัน แป่ว แต่เนื่องจาก Big-O เป็น Asymptotic Notation ที่นิยมใช้กันมากที่สุด หลังจากนี้เราจะมาเสนอตัวอย่างการใช้ Big O กัน

Types of Big O

1. 𝑂(1) (Constant Time) ใช้ในการบ่งบอกว่า Algorithm นั้นมีการกำหนดว่ามีสมาชิก 𝑛 ตัวและถึงแม้ว่า 𝑛 เป็นจำนวนไหนก็ตามตามเงื่อนไข 0 ≤ 𝑛 ≤ 𝑘 โดย 𝑘 ∈ 𝑍 และ 𝑘 ≥ 𝑛 ทำงานได้ 1 รอบ แล้ว n = k+1 ทำงานได้ทั้งหมด 1 รอบจริงๆ

int arr[10] = {1,2,3,5,8,13,21,34,55,68};
System.out.println(Arrays.toString(arr[5]));

2. 𝑂(𝑛) (Linear Time) ใช้ในการบ่งบอกว่า Algorithm นั้นมีการกำหนดว่ามีสมาชิก n ตัว และมีการทำงาน n รอบ ไม่ว่า n จะมีจำนวนเท่าใดก็ตาม

int arr[10] = {1,2,3,5,8,13,21,34,55,68};

for (int i=0; i<arr.length; i++) {
  if (arr[i] == 21) {
    System.out.println("founded: " + arr[i]);
  }
}

3. 𝑂(𝑛²) (Quadratic Time) ใช้ในการบ่งบอกว่า algorithm นั้นมีการกำหนดว่ามีสมาชิก n ตัว และมีการทำงานทั้งหมด n² รอบ เป็นไปในลักษณะของ Nested-Loop

int arr[10] = {1,2,3,5,8,13,21,34,55,68};

for (int i=0; i<arr.length; i++) {
  for (int j=0; j<arr.length; j++) {
    // code
  }
}

4. 𝑂(𝑙𝑜𝑔(𝑛)) (Logarithmic Complexity) ใช้ในการบ่งบอกว่า algorithm นั้นมีการกำหนดว่ามีสมาชิก n ตัว และมีการทำงานทั้งหมด 𝑙𝑜𝑔₂(𝑛) รอบ ซึ่งเป็น Inverse Function ของ Exponential เช่น 2ˣ = 𝑦 ซึ่ง Domain ของฟังก์ชันคือ (−∞,∞) และ Range ของฟังก์ชันคือ (0,∞) สามารถแปลงเป็น 2ʸ = 𝑥 เป้าหมายก็คือเราอยากจะได้ค่า 𝑦 เราจะทำการใช้ logarithm function ลงไป เราก็จะได้ 𝑙𝑜𝑔₂(𝑥) = 𝑦 ซึ่ง Domain ของฟังก์ชันคือ (0,∞) และ Range ของฟังก์ชันคือ (−∞,∞) ตัวอย่างเช่น Binary Search

int arr[] = {1,2,3,5,8,13,21,34,55,68};

int left = 0;
int right = arr.length - 1;
boolean founded = false;
// int center = (left + right) / 2;
int center = left + (right - left) / 2;
int target = 55;

while (left <= right && !founded){
  if (arr[center] < target) {
    left = center + 1;
  } else if (arr[center] > target) {
    right = center - 1;
  } else if (arr[center] == target) {
    System.out.println(target + "is in pos " + center);
    founded = true;
  }
  center = left + (right - left) / 2;
}

5. 𝑂(2ⁿ) (Exponential Time) ใช้ในการบ่งบอกว่า algorithm นั้นการกำหนดว่ามีสมาชิก n ตัว และมีการแจกแจงการทำงานตัวละ 2 ครั้ง ทำให้มีการทำงานทั้งหมดจำนวน 2ⁿ รอบเช่น Recursive Function หรือการ Brute Force ที่มี 2 แบบเช่น True กับ False

int fibbonacci(int n) {
   if(n == 0){
      return 0;
   } else if(n == 1) {
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}

6. 𝑂(𝑛!) (Factorial Time Algorithm) นั้นช้าที่สุด เช่นดังตัวอย่างการหา factorial

for (int i=0; i<factorial(n); i++) {
  System.out.println(i);
}

จะได้เห็นแล้วว่าการทำงานของ Big O แต่ละตัวมีความแตกต่างในเรื่องประสิทธิภาพ ซึ่งการเติบโตจะเป็นดังข้างล่างนี้

https://www.bigocheatsheet.com/

Combination of Function

เนื่องจาก Function แต่ละตัวจะมี Big O ที่ต่างกัน เราสามารถที่จะรวม Function ได้ตามกฎต่อไปนี้

** 𝑔₁(𝑥) และ 𝑔₂(𝑥) ตามที่เห็นเป็นบวกเสมอ หรือ |𝑔₁(𝑥)| และ |𝑔₂(𝑥)|

ถ้า 𝑓₁(𝑥) คือ (𝑔₁(𝑥)) และ 𝑓₂(𝑥) คือ 𝑂(𝑔₂(𝑥)) แล้ว (𝑓₁ + 𝑓₂)(𝑥) คือ 𝑂(𝑚𝑎𝑥(|𝑔₁(𝑥)|,|𝑔₂(𝑥)|))

ตัวอย่างเช่น

𝑇(𝑥)= 3𝑥² + 24𝑥

จะเห็นได้ว่าใน 𝑇(𝑥) จะมี 2 ฟังก์ชัน ทำให้ 𝑓₁(𝑥) = 3𝑥² และ 𝑔₁(𝑥) = 𝑥²

ดังนั้น 𝑓₁(𝑥) = 3𝑔₁(𝑥)

และ 𝑓₂(𝑥) = 24𝑥 และ 𝑔₂(𝑥) = 𝑥

ดังนั้น 𝑓₂(𝑥) = 24𝑔₂(𝑥)

และ 𝑔(𝑥) = (𝑚𝑎𝑥(|𝑔₁(𝑥)|,|𝑔₂(𝑥)|) = 𝑔₁(𝑥) เนื่องจาก Degree สูงกว่า

และ (𝑓₁ + 𝑓₂)(𝑥) = 3𝑔₁(𝑥) + 24𝑔₂(𝑥)

ทำให้ (𝑓₁ + 𝑓₂)(𝑥) ≤ 3𝑔(𝑥) + 24𝑔(𝑥)

(𝑓₁ + 𝑓₂)(𝑥) ≤ 27𝑔(𝑥)

(𝑓₁ + 𝑓₂)(𝑥) ≤ 27𝑥²

(𝑓₁ + 𝑓₂)(𝑥) คือ 𝑂(𝑔(𝑥)) ซึ่งก็คือ 𝑂(𝑥²) เนื่องจากว่า (𝑓₁ + 𝑓₂)(𝑥) = 𝑓(𝑥) ≤ 𝐶𝑔(𝑥) ตามนิยามของ Big-O Notation

ดังนั้น (𝑓₁ + 𝑓₂)(𝑥) คือ 𝑂(𝑚𝑎𝑥(|𝑥²|,|𝑥|)) คือ 𝑂(𝑥²)

ถ้า 𝑓₁(𝑥) คือ (𝑔₁(𝑥)) และ 𝑓₂(𝑥) คือ 𝑂(𝑔₂(𝑥)) แล้ว (𝑓₁ 𝑓₂)(𝑥) คือ 𝑂(𝑔₁(𝑥)𝑔₂(𝑥))

ตัวอย่างเช่น

𝑇(𝑛)= 6𝑛 × 32𝑙𝑜𝑔(𝑛)

จะเห็นได้ว่าใน 𝑇(𝑛) จะมี 2 ฟังก์ชัน ทำให้ 𝑓₁(𝑛) = 6𝑛 และ 𝑔₁(𝑛) = 𝑛

ดังนั้น 𝑓₁(𝑛) = 6𝑔₁(𝑛)

และ 𝑓₂(𝑛) = 32𝑙𝑜𝑔(𝑛) และ 𝑔₂(𝑛) = 𝑙𝑜𝑔(𝑛)

ดังนั้น 𝑓₂(𝑛) = 32𝑔₂(𝑛)

และ (𝑓₁ 𝑓₂)(𝑛) ≤ 6𝑔₁(𝑛) × 32𝑔₂(𝑛)

(𝑓₁ 𝑓₂)(𝑛) ≤ 192𝑔₁(𝑛)𝑔₂(𝑛)

ดังนั้น (𝑓₁ 𝑓₂)(𝑛) ≤ 192𝑛 𝑙𝑜𝑔(𝑛) ซี่ง 𝑔(𝑛) = 𝑔₁(𝑛)𝑔₂(𝑛) = 𝑛 𝑙𝑜𝑔(𝑛)

(𝑓₁ 𝑓₂)(𝑛) คือ 𝑂(𝑔(𝑛)) ซึ่งก็คือ 𝑂(𝑛 𝑙𝑜𝑔(𝑛)) เนื่องจากว่า (𝑓₁ 𝑓₂)(𝑛) = 𝑓(𝑛) ≤ 𝐶𝑔(𝑛) ตามนิยามของ Big-O Notation

ดังนั้น (𝑓₁ 𝑓₂)(𝑛) คือ 𝑂(𝑔₁(𝑛)𝑔₂(𝑛)) คือ 𝑂(𝑛 𝑙𝑜𝑔(𝑛))

สรุป

1. Big O Notation คือการวัดประสิทธิภาพของ Algorithm ก็คือ Time Complexity ในรูปแบบหนึ่ง
2. การพิสูจน์ให้ 𝑝(𝑛) เมื่อ 𝑛 = 1 เป็นจริงโดย 𝑛 ∈ 𝑍 และ 𝑝(𝑘) เป็นจริงโดย 𝑘 ∈ 𝑍 แล้ว 𝑝(𝑘 + 1) เป็นจริงเป็นอุปนัยเชิงคณิตศาสตร์ (Mathematical Induction)
3. 𝑂(𝑛) เมื่อ 𝑛 ∈ 𝑍 และ 𝑛 ≥ 1 เป็นเซทนะครับ