Introduction & 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(\cdots)$ โดยจุดสามจุดแสดงถึงฟังก์ชันใด ๆ
• โดยทั่วไปแล้ว ตัวแปร $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^2)$

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$ และ $\lceil n/2 \rceil$ ครั้ง แต่ 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^2)$

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^2)$ และ $O(n)$
• ดังนั้นคอขวดจะเป็น $O(n^2)$

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

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

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

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

• จากตารางนี้ time complexity คือ $1+2+4+\cdots+2^{n-1} = 2^n-1 = O(2^n)$

Complexity classes

• รายการต่อไปนี้รวม time complexity ของอัลกอริทึมที่เจอบ่อย
• $O(1)$ constant-time algorithm
  • เวลาที่ใช้ในการรันจะเป็น constant ซึ่งไม่สนใจขนาดของ input
  • ยกตัวอย่างเช่นอัลกอริทึมที่มีสูตรคำนวณคำตอบโดยไม่ต้องทำซ้ำใด ๆ
• $O(\log n)$ logarithmic algorithm
  • อัลกอริทึมแบบ logarithmic ส่วนใหญ่จะหารครึ่งขนาดของ input ที่จำเป็นต้องพิจารณาในแต่ละขั้นตอน
  • เวลาที่ใช้ในการรันจะเป็น logarithmic เนื่องจาก $\log_2 n$ เท่ากับจำนวนครั้งที่หาร $n$ ด้วย 2 จนกว่าจะเป็น 1
• $O(\sqrt n)$ square root algorithm
  • ช้ากว่า $O(\log n)$ แต่เร็วกว่า $O(n)$
  • เป็นกรณีที่หารขนาด input $n$ ด้วย $\sqrt n = n/\sqrt n$
• $O(n)$ linear algorithm
  • อัลกอริทึมแบบ linear จะวนใน input เป็นจำนวนครั้งที่แน่นอน
  • ส่วนใหญ่แล้วจะเป็น time complexity ที่ค่อนข้างดี เนื่องจากปกติแล้วจะจำเป็นต้องอ่านค่าทุกค่าใน input
• $O(n \log n)$
  • ส่วนใหญ่จะเกิดจากการเรียงข้อมูล
  • หรือ data structure ที่ใช้ $O(\log n)$ ในแต่ละ operation
• $O(n^2)$ quadratic algorithm
  • ส่วนใหญ่ใช้ลูปสองชั้น
  • เช่นการพิจารณาทุกคู่ของ input
• $O(n^3)$ cubic algorithm
  • ลูปสามชั้น
• $O(2^n)$
  • การพิจารณาทุก subsets ของ input
  • ตัวอย่างเช่น subsets ของ $\{1,2,3\}$ คือ $\emptyset$, $\{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^5$
• ถ้า time complexity เป็น $O(n^2)$ อัลกอริทึมนี้จะรันทั้งหมด $(10^5)^2=10^{10}$ คำสั่ง
• ซึ่งโดยคร่าวใช้เวลาประมาณสิบวินาที ซึ่งจะช้าเกินไปสำหรับโจทย์ข้อนี้
• ในอีกทางหนึ่ง หากว่าเรารู้ขนาด input แล้ว เราสามารถเดา time complexity ของอัลกอริทึมที่ใช้แก้ปัญหาได้เช่นกัน
• ตารางต่อไปนี้บอกการประเมินที่พบบ่อยในกรณีที่ให้เวลาในการคำนวณหนึ่งวินาที
• ยกตัวอย่างเช่น หากขนาดของ input เป็น $n=10^5$ time complexity ที่ต้องการจากอัลกอริทึมก็คือ $O(n)$ หรือ $O(n \log n)$
• ด้วยความรู้นี้จะทำให้คิดอัลกอริทึมได้ง่ายขี้นจากการตัดอัลกอริทึมที่ใช้เวลานานออก

ตัวแปร constant

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

space complexity

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