CoE KKU

ในหัวข้อนี้จะพิสูจน์ให้เห็นว่าอัลกอริทึมใด ๆ ของการจัดเรียงที่ใช้เฉพาะการเปรียบเทียบค่าจะต้องใช้จำนวนครั้งการเปรียบเทียบค่าเป็น W (N log N) ครั้ง (ซึ่งก็คือเวลาที่ใช้นั่นเอง) ในกรณี worst-case ซึ่งการพิสูจน์นี้ยังสามารถขยายความเพื่อแสดงให้เห็นว่าแม้กรณีเฉลี่ยก็ต้องใช้จำนวนครั้งของของเทียบค่าเป็น W (N log N) สิ่งที่จะพิสูจน์ คือ อัลกอริทึมของการจัดเรียงค่าที่ใช้เฉพาะการเปรียบเทียบค่านั้น ต้องใช้จำนวนครั้งการในการเปรียบเทียบค่าเท่ากับ $log\ N!$ ครั้งในกรณี worst case และใช้ log N! ครั้งในกรณีเฉลี่ย และเราสมมุติให้ค่าทั้งหมด N ค่าไม่ซ้ำกัน

Decision tree ใช้เป็นเครื่องมือหนึ่งในการพิสูจน์ขอบเขตล่าง ในกรณีของเรา decision tree เป็น binary tree และโนดแต่ละโนดของทรีเป็นเซตของวิธีที่เป็นไปได้ทั้งหมดของการจัดลำดับของค่าตามวิธีที่ใช้เครื่องหมายการเปรียบเทียบค่าระหว่างสมาชิก และผลที่ได้จากการเปรียบเทียบค่าแต่ละคำตอบคือ tree edges

รูปที 7.17 แสดง algorithm ที่ใช้ในการจัดเรียงค่า 3 ค่า คือ a, b, และ c โดยมีสถานะเริ่มต้นที่รากของ tree โดยที่โนดรากจะยังไม่มีการเปรียบเทียบค่าเกิดขึ้น ดังนั้นลำดับค่าที่เป็นไปได้ทั้งหมดถือเป็นลำดับที่ถูกต้องหมด ในกรณีของเราให้มีการเทียบค่าครั้งแรกเป็นการเทียบค่าระหว่าง a และ b ผลที่ได้อาจเป็นไปได้สองทางซึ่งนำไปสู่สถานะ 2 สถานะที่เป็นไปได้ ถ้า a < b ก็จะเหลือทางที่เป็นไปได้อีก 3 ทาง คือโนดหมายเลข 2 และถ้าการทำงานมาถึงโนดที่ 2 เราก็จะทำการเปรียบเทียบค่า a และ c ถ้า a > c การทำงานจะมาถึงโนด 5 ซึ่งเป็นสถานะคำตอบและอัลกอริทึมจะหยุดทำงานเนื่องจากขณะนี้จะเหลือลำดับของค่าเพียงลำดับเดียวเท่านั้น แต่ถ้า a < c (ที่โนด 2) ก็จะต้องมีการเทียบค่าต่อไปในโนด 4

อัลกอริทึมของการจัดเรียงใด ๆ ที่ใช้การเทียบค่าก็สามารถแสดงได้ด้วย decision tree ได้ แต่การเขียนรูป decision tree ทำได้ในกรณีที่จำนวนข้อมูลที่จะทำการจัดเรียงมีปริมาณน้อยมาก ๆ เท่านั้น จะเห็นได้จาก decision tree ว่าจำนวนครั้งของการเปรียบเทียบค่าในการจัดเรียงจะเท่ากับ depth ของ leaf ที่อยู่ลึกที่สุด ในตัวอย่างของเราข้างบนต้องใช้การเทียบค่า 3 ครั้งสำหรับกรณี worst case ส่วนค่าเฉลี่ยจำนวนครั้งของการเทียบค่าเท่ากับ depth เฉลี่ยของ leaves ทั้งหมด ในการพิสูจน์ขอบเขตล่างนั้นสิ่งที่ต้องใช้ คือคุณสมบัติของ tree นั่นเอง

LEMMA 7.1
ถ้า T เป็น binary tree ที่มีค่า depth = d แล้ว T จะมีจำนวน leaf มากที่สุดเท่ากับ 2d leaves
PROOF:
พิสูจน์โดย induction ถ้า d = 0 แสดงว่ามี leaf มากที่สุดหนึ่งตัว นี่เป็น basis ซึ่งแสดงว่าจริง มิฉะนั้น ทรีนี้ก็จะประกอบด้วยราก (ซึ่งไม่ใช่ leaf) และมี left และ right subtree ซึ่งแต่ละ subtree มี depth ได้สูงสุดคือ d – 1 เท่านั้น ดังนั้น ด้วย induction hypothesis แต่ละ subtree นั้นจะมี leaf ได้สูงสุดเท่ากับ $2^{d-1}$ leaves เท่านั้น และเมื่อรวมกันจะได้ leaf สูงสุดเท่ากับ $2^d$ leaves เป็นการพิสูจน์ Lemma

LEMMA 7.2
binary tree ที่มี L leaves ต้องมี depth อย่างน้อย ⌈log L⌉
PROOF:
เป็นจริงด้วย lemma 7.1

THEOREM 7.6
อัลกอริทึมของการจัดเรียงค่าที่ใช้เฉพาะการเปรียบเทียบค่าระหว่างข้อมูลสมาชิกจะต้องใช้จำนวนครั้งในการเปรียบเทียบค่าอย่างน้อย ⌈log n!⌉ ครั้งในกรณี worst case PROOF:
decision tree ที่ใช้ในการจัดเรียงข้อมูล N ตัว มี n! leaves ดังนั้นจึงเป็นจริงด้วย lemma 7.2

THEOREM 7.7
อัลกอริทึมของการจัดเรียงค่าที่ใช้เฉพาะการเปรียบเทียบค่าของข้อมูลสมาชิกต้องใช้การเทียบค่าเป็น $\Omega(N\ log\ N)$ ครั้ง PROOF:
จากทฤษฎีที่แล้ว ต้องใช้การเทียบค่า log n! ครั้ง และ \begin{align*} log⁡(N!) & = log⁡(N(N-1)(N-2) ⋯ (2)(1))\\ & = log⁡(N) + log⁡(N-1) + log⁡(N-2) + ⋯ + log(⁡2) + log(⁡1)\\ & ≥ log⁡(N) + log⁡(N-1) + log⁡(N-2) + ⋯ + log⁡(N/2)\\ & ≥ N/2\ log(N/2)\\ & ≥ N/2\ log⁡(N/2) - N/2\\ & = \Omega(N\ log\ ⁡N) \end{align*} หรืออาจกล่าวได้ว่า $log⁡(N!)= O(N\ log⁡(N))$ ดังนี้ \begin{align*} log⁡(N!) & = log⁡(N) + log⁡(N-1) + log⁡(N-2) + ⋯ + log⁡(2) + log⁡(1)\\ & ≤ log(N)+log⁡(N)+log⁡(N)+⋯+log⁡(N)\ \ \ \text{N-terms}\\ & ≤ N\ log⁡(N) \end{align*} ดังนั้น $log(N!)=\Omega(N\ log⁡(N))$ และถ้า $log(N!)=\Omega(N\ log\ ⁡N)$ และ $log(N!)=O(N\ log\ N)$ ก็หมายความว่า $log(N!)=\Theta(N\ log⁡\ N)$