Big O Notation | คู่มือโอลิมปิกคอมพิวเตอร์

Big-O Notation

introduction
time complexity
space complexity

การเขียนโปรแกรมแข่งขันประกอบด้วย

การออกแบบอัลกอริทึม
การ implement สร้างอัลกอริทึม

การออกแบบอัลกอริทึม

ใช้ทักษะ problem solving
และ mathematical thinking
โดยจำเป็นต้องวิเคราะห์ปัญหาและแก้ปัญหาอย่างสร้างสรรค์
อัลกอริทึมที่ใช้แก้ปัญหาจะต้องถูกต้องแล้วมีประสิทธิภาพ
หลักสำคัญของโจทย์ปัญหาส่วนใหญ่จะเป็นการคิดสร้างสรรค์อัลกอริทึมที่มีประสิทธิภาพ
ความรู้ทางทฤษฎีของอัลกอริทึมเป็นสิ่งสำคัญต่อนักเขียนโปรแกรมเชิงแข่งขัน
โดยทั่วไปแล้ว เฉลย (solution) ของปัญหาหนึ่งนั้นจะเป็นการใช้เทคนิคที่แพร่หลายร่วมกับ insight ใหม่ตามโจทย์
เทคนิคในการเขียนโปรแกรมเชิงแข่งขันยังเป็นพื้นฐานในการวิจัยสายอัลกอริทึมอีกด้วย

การ implement สร้างอัลกอริทึม

ใช้ทักษะการเขียนโปรแกรมที่ดี
ในการเขียนโปรแกรมเชิงแข่งขันนั้น เฉลยจะถูกตรวจสอบอัลกอริทึมด้วยชุดทดสอบ
ดังนั้น การที่ไอเดียของอัลกอริทึมถูกต้องเท่านั้นยังไม่เพียงพอ แต่การ implement สร้างอัลกอริทึมจะต้องถูกต้องด้วยเช่นกัน
style ในการเขียนโค้ดในการแข่งขันจะตรงไปตรงมาและกระทัดรัด
โปรแกรมควรถูกเขียนอย่างรวดเร็ว เพราะเวลาจะมีอยู่อย่างจำกัด

การวิเคราะห์อัลกอรึทึม

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

เพื่อพิจารณาเลือกใช้ได้อย่างถูกวิธี

Motivation problem

เราจะรู้ได้อย่างไรว่าโค้ดใดนี้มีประสิทธิภาพที่ดีกว่ากัน ระหว่าง

for (int i = 1; i <= n; i++) {
  for (int j = i + 1; j <= n; j++) {
    // code
  }
}

และ

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j += i) {
    // code
  }
}

ประสิทธิภาพของอัลกอริทึม

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

และส่วนมากจะให้จความสำคัญกับการใช้เวลาอย่างมีประสิทธิภาพมากกว่าเนื้อที่

Big O Notation หรืออันดับขนาด (order of magnitude) เป็นเครื่องมือหลักในการวิเคราะห์อัลกอริทึม

Time complexity

ประสิทธิภาพของอัลกอริทึมเป็นสิ่งสำคัญในการเขียนโปรแกรมเชิงแข่งขัน
โดยทั่วไปนั้นจะง่ายที่จะออกแบบอัลกอริทึมที่แก้ปัญหาได้ช้า แต่ความท้าทายจะอยู่ที่อยากออกแบบอัลกอริทึมที่รวดเร็ว
หากอัลกอริทึมนั้นช้าเกินไป จะได้รับคะแนนบางส่วนหรรือไม่ได้เลย
การคาดการณ์เวลาที่อัลกอริทึมใช้สำหรับ input ต่าง ๆ
หลักการคือการแสดงประสิทธิภาพในรูปแบบของฟังก์ชันโดยมีพารามิเตอร์เป็นขนาดของ input
ด้วยการคำนวณ time complexity เราสามารถตรวจสอบความเร็วของอัลกอริทึมได้โดยไม่ต้อง implement ขึ้นมาก่อน

กฏของการคำนวณ

time complexity ของอัลกอริทึมหนึ่งจะถูกแทนด้วยสัญลักษณ์ O(⋯) โดยจุดสามจุดแสดงถึงฟังก์ชันใด ๆ
โดยทั่วไปแล้ว ตัวแปร n แสดงถึงขนาดของ input
ตัวอย่างเช่น หาก input เป็นอาเรย์ของตัวเลข n จะเป็นขนาดของอาเรย์นั้น และหาก input เป็น string n จะเป็นความยาวของ string นั้น

การวนซ้ำ

เหตุผลที่พบบ่อยจากการที่อัลกอริทึมช้าเกินไปเกิดจากการใช้การวนซ้ำจำนวนมากสำหรับ input
ยิ่งวนซ้ำหลายชั้น อัลกอริทีมจะยิ่งช้า
หากมีการวนซ้ำ k ชั้น time complexity จะเป็น O(n^k)

ตัวอย่างเช่น time complexity ของโค้ดด้านล่างจะเป็น O(n)

for (int i = 1; i <= n; i++) {
  // code
}

และ time complexity ของโค้ดด้านล่างนี้ O(n²)

for (int i = 1; i <= n; i++) {    // ชั้นที่ 1
  for (int j = 1; j <= n; j++) {  // ชั้นที่ 2
    // code
  }
}

Order of magnitude

time complexity จะไม่สนใจจำนวนรอบเป๊ะ ๆ ภายใน loop แต่จะสนใจเฉพาะ order of magnitude
ในตัวอย่างต่อไปนี้ จำนวนรอบในการวนเป็น 3n, n + 5 และ $l\frac{n}{2}r$ ครั้ง แต่ time complexity นั้นเท่ากันคือ O(n)

for (int i = 1; i <= 3*n; i++) {
  // code
}

for (int i = 1; i <= n+5; i++) {
  // code
}

for (int i = 1; i <= n; i += 2) {
  // code
}

ในอีกตัวอย่างหนึ่ง time complexity ของโค้ดต่อไปนี้เป็น O(n²)

for (int i = 1; i <= n; i++) {
  for (int j = i+1; j <= n; j++) {
   // code
  }
}

Phase

ถ้าอัลกอริทึมประกอบไปด้วยหลาย phase ติดต่อกันแล้ว complexity จะเป็น time complexity ที่สูงสุดของ phase หนึ่ง
เนื่องจาก bottleneck จะอยู่ที่ phase ที่ช้าที่สุด
ตัวอย่างเช่น โค้ดต่อไปนี้ประกอบด้วย 3 phases ที่มี time complexity O(n), O(n²) และ O(n)
ดังนั้นคอขวดจะเป็น O(n²)

for (int i = 1; i <= n; i++) {
  // code O(n)
}
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
    // code O(n^2)
  }
}
for (int i = 1; i <= n; i++) {
  // code O(n)
}

กรณีหลายตัวแปร

บางครั้ง time complexity จะขึ้นอยู่กับหลายปัจจัย
ซึ่งเราสามารถใช้หลายตัวแปรแทนได้
ตัวอย่างเช่น time complexity ของโค้ดด้านล่างเป็น O(nm)

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    // code
  }
}

Recursion

time complexity ของฟังก์ชัน recursive จะขึ้นอยู่กับจำนวนครั้งที่ฟังก์ชันนั้นถูกเรื่องและ time complexity ของการเรียกฟังก์ชันแต่ละครั้ง
ซึ่งจะนำสองค่านี้มาคูณกัน
ยกตัวอย่างเช่น

void f(int n) {
  if (n == 1) return;
  f(n-1);
}

การเรียกฟังก์ชัน f(n) จะเรียกฟังก์ชันทั้งหมด n ครั้ง และแต่ละครั้งจะใช้ time complexity O(1)
ดังนั้น time complexity รวมคือ O(n) ⋅ O(1) = O(n)
อีกตัวอย่าง เช่น

void g(int n) {
  if (n == 1) return;
  g(n-1);
  g(n-1);
}

ในกรณีนี้ การเรียกฟังก์ชั้นแต่ละครั้งจะเรียกเพิ่มอีกสองครั้ง ยกเว้นกรณี n = 1
พิจารณาสิ่งที่เกิดขึ้นจากการเรียก g ด้วยพารามิเตอร์ n
ตารางด้านล่างแสดงจำนวนการเรียก function ที่เกิดขึ้น

function call	number of calls
g(n)	1
g(n − 1)	2
g(n − 2)	4
⋯	⋯
g(1)	2^n − 1

จากตารางนี้ time complexity คือ 1 + 2 + 4 + ⋯ + 2^n − 1 = 2ⁿ − 1 = O(2ⁿ)

Complexity classes

รายการต่อไปนี้รวม time complexity ของอัลกอริทึมที่เจอบ่อย
O(1) constant-time algorithm
- เวลาที่ใช้ในการรันจะเป็น constant ซึ่งไม่สนใจขนาดของ input
- ยกตัวอย่างเช่นอัลกอริทึมที่มีสูตรคำนวณคำตอบโดยไม่ต้องทำซ้ำใด ๆ
O(log n) logarithmic algorithm
- อัลกอริทึมแบบ logarithmic ส่วนใหญ่จะหารครึ่งขนาดของ input ที่จำเป็นต้องพิจารณาในแต่ละขั้นตอน
- เวลาที่ใช้ในการรันจะเป็น logarithmic เนื่องจาก log₂n เท่ากับจำนวนครั้งที่หาร n ด้วย 2 จนกว่าจะเป็น 1
$O\left( \sqrt{n} \right)$ square root algorithm
- ช้ากว่า O(log n) แต่เร็วกว่า O(n)
- เป็นกรณีที่หารขนาด input n ด้วย $\sqrt{n} = \frac{n}{\sqrt{n}}$
O(n) linear algorithm
- อัลกอริทึมแบบ linear จะวนใน input เป็นจำนวนครั้งที่แน่นอน
- ส่วนใหญ่แล้วจะเป็น time complexity ที่ค่อนข้างดี เนื่องจากปกติแล้วจะจำเป็นต้องอ่านค่าทุกค่าใน input
O(nlog n)
- ส่วนใหญ่จะเกิดจากการเรียงข้อมูล
- หรือ data structure ที่ใช้ O(log n) ในแต่ละ operation
O(n²) quadratic algorithm
- ส่วนใหญ่ใช้ลูปสองชั้น
- เช่นการพิจารณาทุกคู่ของ input
O(n³) cubic algorithm
- ลูปสามชั้น
O(2ⁿ)
- การพิจารณาทุก subsets ของ input
- ตัวอย่างเช่น subsets ของ {1, 2, 3} คือ
⌀, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} และ {1, 2, 3}.
O(n!)
- การพิจารณาทุกการจัดเรียงของ input
- ตัวอย่างเช่นการจัดเรียงของ {1, 2, 3} คือ
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) and (3, 2, 1).

การประเมินประสิทธิภาพ

จากการคำนวณ time complexity ของอัลกอริทึมนั้นทำให้สามารถตรวจสอบประสิทธิภาพของอัลกอริทึมก่อนการ implement ได้
จุดอ้างอิงคร่าวๆ ให้คาดว่า C++ สามารถรันได้ 1, 000, 000, 000 (พันล้าน) คำสั่งต่อหนึ่งวินาที
ตัวอย่างเช่นถ้าข้อจำนวนของโจทย์นั้นให้เวลาในการคำนวณหนึ่งวินาทีและ n = 10⁵
ถ้า time complexity เป็น O(n²) อัลกอริทึมนี้จะรันทั้งหมด (10⁵)² = 10^{10} คำสั่ง
ซึ่งโดยคร่าวใช้เวลาประมาณสิบวินาที ซึ่งจะช้าเกินไปสำหรับโจทย์ข้อนี้
ในอีกทางหนึ่ง หากว่าเรารู้ขนาด input แล้ว เราสามารถเดา time complexity ของอัลกอริทึมที่ใช้แก้ปัญหาได้เช่นกัน
ตารางต่อไปนี้บอกการประเมินที่พบบ่อยในกรณีที่ให้เวลาในการคำนวณหนึ่งวินาที
ยกตัวอย่างเช่น หากขนาดของ input เป็น n = 10⁵ time complexity ที่ต้องการจากอัลกอริทึมก็คือ O(n) หรือ O(nlog n)
ด้วยความรู้นี้จะทำให้คิดอัลกอริทึมได้ง่ายขี้นจากการตัดอัลกอริทึมที่ใช้เวลานานออก

input size	required time complexity
N ≤ 10	O(N!)
N ≤ 20	O(2^N)
N ≤ 500	O(N³)
N ≤ 5000	O(N²)
N ≤ 10⁶	O(Nlog N) or O(N)
N is large	O(1) or O(log N)

ตัวแปร constant

อย่างไรก็ตาม ควรจำว่า time complexity นั้นแค่เป็นการประมาณประสิทธิภาพเท่านั้นเพราะไม่คิด constant factors
ตัวอย่างเช่น อัลกอริทึมที่ใช้เวลา O(n) อาจมีการคำนวณทั้งหมด $\frac{n}{2}$ หรือ 5n คำสั่ง
ซึ่งเป็นสิ่งสำคัญต่อเวลาที่ใช้จริงในการรันอัลกอริทึม

space complexity

ใช้ Big O Notation เป็นเครื่องมือเช่นกัน
เปลี่ยนจากการนับขนาดเวลา เป็นนับขนาด memory เช่น
- ขนาดของ array ที่เราประกาศ

Function Stack and Queue