Alpha beta pruning Big O

กระทู้คำถาม

คณิตศาสตร์

ผมไม่เข้าใจวิธีหา Big O ของ Alpha beta pruning ครับ O = b^(d/2) เลยครับใครพอเข้าใจเรื่องนี้บ้างครับ

ถูกใจให้พอยต์

สมาชิกหมายเลข 2857114

สมาชิกหมายเลข 5212378 ถูกใจ

คำตอบที่ได้รับเลือกจากเจ้าของกระทู้

ความคิดเห็นที่ 1

ที่บอกว่า time complexity = O(b^(d/2)) นี่เป็น best case นะครับ ห้ามเอาไปรวมกับ general time complexity (เช่น ถ้าบอกว่า time complexity ของ alpha beta pruning เท่าไหร่ ต้องตอบ worst case คือ O(b^d) ห้ามตอบ O(b^(d/2))

คือ มันจะข้ามการ search แบบชั้นเว้นชั้นเลย เพราะมันจะ prune ได้ตั้งแต่ node แรกของชั้นนั้น

ดังนั้น time complexity จะออกมาในรูปแบบ (b*1*b*1... 1 หรือ b (ชั้นคู่-คี่)) มันเลยเหลือ b^(d/2)