計(jì)算機(jī)算法導(dǎo)論_第8章(編輯修改稿)
2025-02-16 11:56 本頁面
【文章內(nèi)容簡介】 heapsort. The best worstcase running time that we’ve seen for parison sorting is O(n lg n) . Is O(n lg n) the best we can do? Decision trees can help us answer this question. Decisiontree model A decision tree can model the execution of any parison 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 merg
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1