計(jì)算機(jī)算法導(dǎo)論_第8章-展示頁
2025-01-29 11:56本頁面
【正文】 on sort: ? One tree for each input size n. ? View the algorithm as splitting whenever it pares two elements. ? The tree contains the parisons along all possible instruction traces. ? The running time of the algorithm = the length of the path taken. ? Worstcase running time = height of tree. Lower bound for decisiontree sorting Lower bound for parison sorting Corollary. Heapsort and merge sort are asymptotically optimal parison sorting algorithms. Counting sort Sorting in linear time Counting sort: No parisons between elements. ? Input: A[1 . . n], where A[ j]∈ {1, 2, …, k} . ? Output: B[1 . . n], sorted. ? Auxiliary storage: C[1 . .
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1