neizod's speculation

insufficient data for meaningful answer

เลือกของอันดับที่ต้องการในเวลา $O(n)$

Thursday, September 20, 2018, 11:58 PM

สมมติว่าเรามีเซต $A$ ซึ่งเก็บสิ่งของที่เปรียบเทียบอันดับกันได้อยู่ $n$ ชิ้น เราคงคุ้นเคยกันดีกับอัลกอริทึมสำหรับเลือกสิ่งของชิ้นที่เล็กสุด/ใหญ่สุด (อันดับแรก/สุดท้าย) ที่ทำงานได้ในเวลา $O(n)$ … แต่ถ้าเราต้องการเลือกสิ่งของในอันดับอื่นหละ อัลกอริทึมของเราจะหน้าตาเป็นอย่างไร?

คิดไม่ออกก็เริ่มต้นอัลกอริทึมของเราด้วยการเรียงลำดับสมาชิกทุกตัวบน $A$ ซึ่งทำได้ในเวลา $O(n \log n)$ แล้วหลังจากนั้นก็เลือกสมาชิกตำแหน่งที่ $i \in \{1,2,\dots,n\}$ ภายในเวลา $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)$ และลดลงทีละครึ่งไปเรื่อยๆ

ดังนั้นเวลาที่ใช้ทั้งหมดจะกลายเป็น

ตัวอย่างโค้ดในภาษา 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]

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