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

O(n)

การคูณ

   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^2)

สมุดโทรศัพท์

การเปิดสมุดโทรศัพท์ซึ่งมีรายชื่อเรียงตามตัวอักษรนั้น วิธีที่สิ้นคิดที่สุดคือเปิดไล่ไปเรื่อยๆ วิธีนี้ถ้าต้องการหาชื่อคนสุดท้ายต้องเปิดไล่ไปจนครบทุกคน ฉะนั้นจะใช้เวลาทำงาน 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

O(log n)

กรณีที่เกิดขึ้นได้กับอัลกอริธึม

บางครั้ง 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(n!)

กรณีอื่นๆ

  • 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;
    }
}

References