Initially you place the elements yo

Initially you place the elements you want to sort in the leaves of the tournament tree. Then you fill all the internal nodes with the bigger of the two elements in their respective children. This takes n−1 comparisons.

After that, you have the largest element in the root. So you can remove it and place it in the output. Now all the comparisons where this element was involved have to be redone. This is one comparison per level of the tree, making (logn)−1 comparisons (-1, since on the lowest level, there is only one candidate element left, so you don't need to compare.)

Now the second largest element is at the top and you can repeat the procedure. And so on. In the end you will have made up to logn, i.e. O(logn) comparisons for each of the n elements.

Summing up, we have n−1+n⋅O(logn) comparisons. By the rules of O-notation, that is in O(nlogn).

ผลลัพธ์ (ไทย) 1:

เริ่มต้นคุณสามารถวางองค์ประกอบที่คุณต้องการเรียงลำดับในใบของต้นการแข่งขัน แล้ว คุณกรอกภายในโหนกับใหญ่สององค์ประกอบในลูกที่เกี่ยวข้อง นี้จะเปรียบเทียบ n−1หลังจากนั้น คุณต้องมีองค์ประกอบที่ใหญ่ที่สุดในราก ดังนั้น คุณสามารถลบ และวางผลลัพธ์ ตอนนี้ เปรียบเทียบทั้งหมดที่เกี่ยวข้องกับองค์ประกอบนี้จะต้องเป็นเรดวัน นี่คือหนึ่งการเปรียบเทียบต่อระดับต้น การเปรียบเทียบ −1 (logn) (-1 ตั้งแต่ระดับต่ำ มีองค์ประกอบผู้เดียวซ้าย ดังนั้นคุณไม่จำเป็นต้องเปรียบเทียบ)ตอนนี้เป็นองค์ประกอบอันดับสองที่ด้านบน และคุณสามารถทำซ้ำขั้นตอน และอื่น ๆ ในสุด คุณจะทำค่า logn เช่น O(logn) เปรียบเทียบสำหรับแต่ละองค์ประกอบ nรวม เราได้เปรียบ n−1+n⋅O(logn) โดยกฎของสัญกรณ์โอ ที่อยู่ใน O(nlogn)

ผลลัพธ์ (ไทย) 2:

เริ่มแรกคุณวางองค์ประกอบที่คุณต้องการในการจัดเรียงในใบของต้นไม้การแข่งขัน แล้วคุณเติมเต็มทุกโหนดภายในที่มีขนาดใหญ่ของทั้งสององค์ประกอบในเด็กของตน นี้จะใช้เวลา n-1 เปรียบเทียบ. หลังจากนั้นคุณมีองค์ประกอบที่ใหญ่ที่สุดในราก ดังนั้นคุณสามารถลบออกและวางไว้ในการส่งออก ตอนนี้สิ่งที่เปรียบเทียบองค์ประกอบนี้มีส่วนเกี่ยวข้องจะต้องมีการทำซ้ำ นี้เป็นหนึ่งในการเปรียบเทียบต่อระดับของต้นไม้ทำให้ (logn) เปรียบเทียบ -1 (-1 ตั้งแต่ในระดับต่ำสุดมีเพียงองค์ประกอบหนึ่งของผู้สมัครที่เหลือเพื่อให้คุณไม่ต้องเปรียบเทียบ.) ตอนนี้เป็นองค์ประกอบที่ใหญ่เป็นอันดับสอง อยู่ที่ด้านบนและคุณสามารถทำซ้ำขั้นตอน และอื่น ๆ ในท้ายที่สุดคุณจะได้ทำถึง logn คือ O (logn) เปรียบเทียบสำหรับแต่ละองค์ประกอบที่ n. ข้อสรุปถึงเรามี n-1 + n⋅O (logn) เปรียบเทียบ ตามกฎของ O-สัญกรณ์ที่อยู่ใน O (nlogn)

ผลลัพธ์ (ไทย) 3:

ตอนแรกท่านวางองค์ประกอบที่คุณต้องการเรียงลำดับในใบของต้นไม้ แข่งขัน คุณกรอกข้อมูลทั้งหมดภายในโหนดที่มีขนาดใหญ่ของทั้งสององค์ประกอบในบุตรของตน การเปรียบเทียบนี้ใช้ N − 1 .

หลังจากนั้นคุณจะมีองค์ประกอบที่ใหญ่ที่สุดในราก เพื่อให้คุณสามารถกำจัดมันและวางไว้ในการส่งออก ตอนนี้การเปรียบเทียบทั้งหมดที่เกี่ยวข้องกับองค์ประกอบนี้คือต้องทำใหม่หมด