TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 13.6 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of sorting lower bound. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Sorting Lower Bound 3/29/14 21:28 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Sorting Lower Bound © 2014 Goodrich, Tamassia, Goldwasser Sorting Lower Bound 1 Comparison-Based Sorting ! Many sorting algorithms are comparison based. n   n   They sort by making comparisons between pairs of objects Examples: bubble-sort, selection-sort, insertion-sort, heap-sort, merge-sort, quick-sort, . ! Let us therefore derive a lower bound on the running time of any algorithm that uses comparisons to sort n elements, x1, x2, , xn. Is xi < xj? no yes © 2014 Goodrich, Tamassia, Goldwasser Sorting Lower Bound 2 1 Sorting Lower Bound 3/29/14 21:28 Counting Comparisons ! Let us just count comparisons then. ! Each possible run of the algorithm corresponds to a root-to-leaf path in a decision tree xi < xj ? xa < xb ? xe < xf ? © 2014 Goodrich, Tamassia, Goldwasser xc < xd ? x m < xo ? xk < xl ? xp < xq ? Sorting Lower Bound 3 Decision Tree Height ! The height of the decision tree is a lower bound on the running time ! Every input permutation must lead to a separate leaf output ! If not, some input 4 5 would have same output ordering as 5 4 , which would be wrong ! Since there are n!=1⋅2 ⋅ ⋅n leaves, the height is at least log (n!) minimum height (time) xi < x j ? xa < xb ? xc < xd ? log (n!) xe < xf ? © 2014 Goodrich, Tamassia, Goldwasser xk < xl ? n! Sorting Lower Bound xm < xo ? xp < xq ? 4 2 Sorting Lower Bound 3/29/14 21:28 The Lower Bound ! Any comparison-based sorting algorithms takes at least log (n!) time ! Therefore, any such algorithm takes time at least n 2 ⎛ n ⎞ log (n!) ≥ log ⎜ ⎟ = (n / 2) log (n / 2). ⎝ 2 ⎠ ! That is, any comparison-based sorting algorithm must run in Ω(n log n) time. © 2014 Goodrich, Tamassia, Goldwasser Sorting Lower .

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Sorting lower bound
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming