การประเมินประสิทธิภาพ: Big O และ Θ

นึกภาพก่อน

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

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

ตัวอย่าง: หาผลต่างมากสุด

โจทย์: หาผลต่างที่มากที่สุดระหว่างข้อมูลสองตัวใด ๆ ในอาเรย์ขนาด n

วิธีที่ 1 เทียบทุกคู่:

java

int max = 0;
for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
    if (Math.abs(d[i] - d[j]) > max) max = Math.abs(d[i] - d[j]);

ลูปซ้อนสองชั้น ทำงานประมาณ n × n = n² ครั้ง

วิธีที่ 2 หาค่ามากสุดกับค่าน้อยสุดแล้วลบกัน:

java

int max = d[0], min = d[0];
for (int i = 1; i < n; i++) {
  if (d[i] > max) max = d[i];
  if (d[i] < min) min = d[i];
}
return max - min;

ลูปชั้นเดียว ทำงานประมาณ n ครั้ง

เมื่อ n = 1,000 วิธีแรกทำ 1,000,000 ครั้ง วิธีที่สองทำ 1,000 ครั้ง

อัตราการเติบโต

เรียงจากโตช้าไปโตเร็ว:

text

log n  ≺  n  ≺  n²  ≺  2ⁿ

n	log₂ n	n	n²	2ⁿ
8	3	8	64	256
16	4	16	256	65,536
1,024	10	1,024	1,048,576	มากเกินจะเขียน

เราสนใจเฉพาะ รูปแบบการโต ไม่สนค่าคงที่และพจน์เล็ก ๆ งาน 3n + 5 ครั้ง กับ n ครั้ง โตแบบเดียวกัน คือ "เชิงเส้น"

Big O กับ Θ

O (Big O): จำนวนการทำซ้ำ ไม่เกิน ค่านั้น เป็นขอบเขตบน ใช้เมื่อจำนวนรอบไม่แน่นอน อาจจบเร็วกว่าได้
Θ: จำนวนการทำงานเป็นค่า แน่นอน ตามนั้น

ตัวอย่าง:

contains ไล่หาข้อมูล อาจพบที่ช่องแรก หรือไล่จนครบ n ช่อง → O(n) (ไม่เกิน n)
size() อ่านตัวแปรหนึ่งตัวเสมอ → Θ(1) (คงที่แน่นอน)
constructor สร้างอาเรย์ c ช่อง ต้องตั้งค่าครบทุกช่องเสมอ → Θ(c)

วิเคราะห์ ArrayCollection

เมท็อด	เวลา	วิธีคิด
`ArrayCollection(c)`	Θ(c)	สร้างอาเรย์ c ช่อง
`isEmpty()`, `size()`	Θ(1)	คำสั่งเดียว ไม่มีลูป
`add(e)`	Θ(1)	ใส่ท้าย ไม่มีลูป (ครั้งที่ต้องขยายอาเรย์เป็น O(n))
`contains(e)`	O(n)	ลูปใน `indexOf` หยุดเมื่อพบ
`remove(e)`	O(n)	ค้น O(n) แล้วลบ Θ(1) รวมกันได้ O(n)

เมื่อบวกเวลาของหลายขั้นตอน ให้ถือพจน์ที่โตเร็วที่สุด: O(n) + Θ(1) = O(n)

สรุปวิธีวัดแบบคร่าว ๆ (ตามสไลด์)

มีประโยคทำซ้ำ (for, while, do while) ที่ไม่ทราบจำนวนรอบแน่นอน → เวลาเป็น O(n) (ถือว่าใช้เวลานาน)
มีประโยคที่นับจำนวนได้แน่นอน → เวลาเป็น Θ ของจำนวนนั้น
ประโยคสร้างอ็อบเจกต์ ใช้เวลาตามขนาดที่สร้าง เช่น new ArrayCollection(100)

ตัวอย่างไล่ทีละขั้น

วิเคราะห์ remove:

java

public void remove(Object e) {
  int i = indexOf(e);                       // (ก)
  if (i != -1) {
    elementData[i] = elementData[--size];   // (ข)
    elementData[size] = null;               // (ค)
  }
}

(ก) เรียก indexOf ซึ่งมีลูปไล่เทียบ จำนวนรอบไม่แน่นอน อย่างมาก n รอบ → O(n)
(ข) และ (ค) เป็นคำสั่งกำหนดค่าอย่างละครั้ง → Θ(1)
รวม: O(n) + Θ(1) = O(n)

ข้อสังเกต: ตัว "การลบ" เร็วมาก แต่ทั้งเมท็อดช้าเพราะต้องค้นก่อน

จุดที่มักพลาด

1. เห็นลูปแล้วตอบ O(n) ทันที

ต้องดูว่าลูปวนกี่รอบ ลูปซ้อนสองชั้นที่วน n ทั้งคู่เป็น O(n²) ลูปที่วนจำนวนคงที่ (เช่น 10 รอบเสมอ) เป็น Θ(1)

2. ใช้ Θ กับงานที่อาจจบก่อน

contains ไม่ใช่ Θ(n) เพราะอาจพบตั้งแต่ช่องแรก ใช้ O(n) จึงถูก

3. คิดว่า O(n) แปลว่าต้องทำ n ครั้งเสมอ

O คือขอบเขตบน "ไม่เกิน" เท่านั้น

4. นับค่าคงที่

2n, n + 100 และ n/2 ล้วนเป็น O(n)

5. ลืมเวลาของเมท็อดที่ถูกเรียก

contains มีบรรทัดเดียว แต่บรรทัดนั้นเรียก indexOf ที่มีลูป

ที่มา: COLLECTION_1_2n.pdf หน้า 60–73