418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 7

อินพุต: ลำดับของจำนวนเต็ม $n\,$ จำนวน และช่วง$[p,q]\,$

เอาพุต: จำนวนของลำดับย่อยที่มีพิสัยในช่วง$[p,q]\,$

แนวคิด ข้อนี้วัตถุที่เราสนใจคือ ช่วง เรามีวิธีในการหาช่วงแล้วในห้องเรียน เราจะใช้วิธีนั้นกัน ค่าของวัตถุที่เราสนใจก็คือ การนำค่ามากที่สุดในช่วง มาลบกับค่าที่น้อยที่สุดในช่วง ซึ่งวิธีในการหาค่ามากที่สุด กับน้อยที่สุดเราก็เรียนไปแล้วในห้องเรียน และเงื่อนไขในข้อนี้คือ พิสัยอยู่ในช่วง $[p,q]\,$ ดังนั้นเมื่อได้พิสัยของแต่ละช่วงมาแล้ว เราก็ต้องนำมาตรวจสอบว่าอยู่ในช่วงดังกล่าวหรือไม่ ถ้าอยู่ที่เพิ่มตัวนับจำนวนขึ้นไปเรื่อย ๆ

เวลาการทำงานของอัลกอริทึม การหยิบลำดับย่อยแต่ละลำดับมาดู เราใช้ for loop สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก $O(n)\,$ ดังนั้นเวลารวมของสองขั้นตอนนี้คือ$O(n^{3})\,$ ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง $[p,q]\,$ หรือไม่ใช้เวลาอีก $q-p+1\,$ ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น $O(n^{3})\,$