TAILIEUCHUNG - Introduction to Algorithms Second Edition Instructor’s Manual 2nd phần 4

Lựa chọn trong thời gian tuyến tính trường hợp xấu nhất Chúng ta có thể Þnd thứ i phần tử nhỏ nhất trong thời gian O (n) trong trường hợp tồi tệ nhất. Chúng tôi sẽ mô tả bầu S thủ tục làm như vậy. S bầu đệ quy phân vùng mảng đầu vào. Để hoàn thành bằng chứng, chúng tôi chọn c như cn | 9-6 Lecture Notes for Chapter 9 Medians and Order Statistics To complete this proof we choose c such that cn 4 c l an 0 cn 4 an c 2 n c 4 a c 2 c 2 n -y--------- c 4 a 2c n c 4a Thus as long as we assume that T n O 1 for n 2c c 4a we have E T n O n . Therefore we can determine any order statistic in linear time on average. Selection in worst-case linear time We can hnd the ith smallest element in O n time in the worst case. We ll describe a procedure Select that does so. Select recursively partitions the input array. Idea Guarantee a good split when the array is partitioned. Will use the deterministic procedure Partition but with a small modihca-tion. Instead of assuming that the last element of the subarray is the pivot the modihed Partition procedure is told which element to use as the pivot. Select works on an array of n 1 elements. It executes the following steps 1. Divide the n elements into groups of 5. Get n 5 groups Ln 5_ groups with exactly 5 elements and if 5 does not divide n one group with the remaining n mod 5 elements. 2. Find the median of each of the Ln 5 groups Run insertion sort on each group. Takes O 1 time per group since each group has 5 elements. Then just pick the median from each group in O 1 time. 3. Find the median x of the Ln 5 medians by a recursive call to Select. If Ln 5 is even then follow our convention and hnd the lower median. 4. Using the modihed version of Partition that takes the pivot element as input partition the input array around x. Let x be the kth element of the array after partitioning so that there are k 1 elements on the low side of the partition and n k elements on the high side. 5. Now there are three possibilities if i k just return x . If i k return the i th smallest element on the low side of the partition by making a recursive call to Select. If i k return the i k th smallest element on the high side of the partition by making a recursive call to Select. Lecture Notes for Chapter 9 Medians and Order Statistics .

• Kỹ thuật lập trình
• thủ thuật hệ điều hành
• tìm hiểu hệ điều hành
• thủ thuật windows
• lập trình windows
• lập trình ứng dụng
• lập trình máy tính
• thủ thuật lập trình
• mẹo hay cho lập trình
• bí quyết lập trình
• thủ thuật máy tính
• phần mềm máy tính
• quản trị hệ thống
• hệ điều hành linux
• hệ điều hành mac
• mẹo cài hệ điều hành
• hệ điều hành unix
• hệ điều hành windows
• kỹ năng máy tính
• Hệ Điều Hành
• các hệ điều hành Windows
• giáo trình hệ điều hành
• các vấn đề hệ điều hành
• tài liệu hệ điều hành
• Tổng quan về hệ điều hành
• windows 7
• Refresh hệ điều hành Android
• Hệ điều hành Android cũ
• Hệ điều hành Android
• Cài đặt hệ điều hành Android
• Thủ thuật hệ điều hành Android
• Khôi phục hệ điều hành Android
• đồ họa máy tính
• mỹ thuật đa truyền thông
• học hệ điều hành
• cách sử dụng hệ điều hành
• hệ điều hành windows 7
• mẹo hay hệ điều hành