เลือกของอันดับที่ต้องการในเวลา $O(n)$
สมมติว่าเรามีเซต $A$ ซึ่งเก็บสิ่งของที่เปรียบเทียบอันดับกันได้อยู่ $n$ ชิ้น เราคงคุ้นเคยกันดีกับอัลกอริทึมสำหรับเลือกสิ่งของชิ้นที่เล็กสุด/ใหญ่สุด (อันดับแรก/สุดท้าย) ที่ทำงานได้ในเวลา $O(n)$ … แต่ถ้าเราต้องการเลือกสิ่งของในอันดับอื่นหละ อัลกอริทึมของเราจะหน้าตาเป็นอย่างไร?
คิดไม่ออกก็เริ่มต้นอัลกอริทึมของเราด้วยการเรียงลำดับสมาชิกทุกตัวบน $A$ ซึ่งทำได้ในเวลา $O(n \log n)$ แล้วหลังจากนั้นก็เลือกสมาชิกตำแหน่งที่ $i \in \lbrace1,2,\dots,n\rbrace$ ภายในเวลา $O(1)$ ซึ่งจะเป็นอันดับของสิ่งของชิ้นที่เราต้องการได้เลย
ผลพลอยได้จากจากการใช้อัลกอริทึมง่ายๆ ตามข้างต้น คือ เราจะสามารถหาสมาชิกในอันดับใดๆ ก็ได้ตามต้องการในภายหลังด้วยเวลา $O(1)$ ขอเพียงแค่เราเก็บผลลัพธ์การเรียงลำดับไว้นั่นเอง
แต่ถ้าเราต้องการเลือกสิ่งของในอันดับที่สนใจเพียงแค่ชิ้นเดียวหละ? จะทำได้เร็วกว่า $O(n \log n)$ หรือเปล่า?
สังเกตว่าอัลกอริทึมเรียงลำดับเช่น การเรียงลำดับแบบเร็ว (quicksort) ทำงานแบบแบ่งแยกและเอาชนะ หลังจากวิ่งแบ่งของที่มากกว่า-น้อยกว่าไว้สองด้านของตัวหลัก (pivot) ในรอบแรกเสร็จ เราจะได้ว่าตัวหลักที่เลือกมานั้นอยู่ในอันดับที่ถูกต้องแน่นอน นอกจากนี้เรายังรู้ตำแหน่งของตัวหลักอีกด้วย ถึงตอนนี้เราจะดัดแปลงอัลกอริทึมดังกล่าวให้กลายเป็นการเลือกแบบเร็ว (quickselect) โดยดูว่าตำแหน่งตัวหลักนั้นเท่ากับอันดับที่เราต้องการหรือไม่ ถ้าใช่ก็ตอบว่าตัวหลักคือสิ่งของในอันดับที่สนใจได้เลย แต่ถ้าตัวหลักอยู่ในตำแหน่งที่สูงกว่า/ต่ำกว่า เราก็จะเจาะลงไปทำปัญหาย่อย (recursion) บนด้านซ้าย/ขวาเพียงด้านเดียวนั่นเอง
ก่อนจะไปดูความซับซ้อนของเวลาที่ใช้คำนวณ อย่าลืมว่าอัลกอริทึมการเรียงลำดับแบบเร็วมีจุดอ่อนอยู่ที่การเลือกตัวหลัก หากเลือกตัวหลักมาไม่ดีพอ ความลึกของต้นไม้ที่ได้จากการแบ่งแยกและเอาชนะอาจลึกไปได้ถึง $n$ (แทนที่จะลึกแค่ $\log n$) ซึ่งสามารถแก้ได้โดยการเลือกตัวหลักมาแบบสุ่มๆ
การวิเคราะห์เวลาของอัลกอริทึมการเลือกแบบเร็ว เริ่มคิดได้จากรอบแรกที่สลับที่ของแบ่งด้านซ้าย/ขวาเทียบกับตัวหลักใช้เวลาเป็น $O(n)$ เนื่องจากเราเลือกตัวหลักมาแบบสุ่ม ขนาดของปัญหาย่อยทั้งด้านซ้ายและด้านขวาจะเหลือประมาณ $n/2$ การทำงานสลับที่รอบที่สองก็จะใช้เวลาลดลงเหลือ $O(n/2)$ รอบที่สามเหลือ $O(n/4)$ และลดลงทีละครึ่งไปเรื่อยๆ
ดังนั้นเวลาที่ใช้ทั้งหมดจะกลายเป็น
\[\begin{align*} \sum_{i=0}^{\log n} O(n/2^i) &= O(n) + O(n/2) + O(n/4) + \dots + O(n/2^{\log n}) \\ &= O\left( n \sum_{i=0}^{\log n} \frac{1}{2^i} \right) \\ &\le O(2n) = O(n) \end{align*}\]ตัวอย่างโค้ดในภาษา Python
from random import randint
def quickselect(ls, index, lo=0, hi=None):
if hi is None:
hi = len(ls) - 1
if lo == hi:
return ls[lo]
pivot = randint(lo, hi)
ls[lo], ls[pivot] = ls[pivot], ls[lo]
pivot = lo
for run in range(lo+1, hi+1):
if ls[run] < ls[lo]:
pivot += 1
ls[pivot], ls[run] = ls[run], ls[pivot]
ls[lo], ls[pivot] = ls[pivot], ls[lo]
if index < pivot:
return quickselect(ls, index, lo, pivot-1)
elif index > pivot:
return quickselect(ls, index, pivot+1, hi)
else:
return ls[pivot]
เราจะเห็นประโยชน์ของอัลกอริทึมการเลือกแบบเร็วได้อย่างชัดเจน เมื่อต้องวิเคราะห์หรือสร้างอัลกอริทึมที่ใช้ความรู้ทางด้านสถิติมาช่วย เช่น นำไปใช้หาค่ามัธยฐานหรือควอร์ไทล์อย่างรวดเร็วโดยไม่ต้องเรียงลำดับสิ่งของที่มีทั้งหมดเสียก่อน
author