摘要: 二路歸并的遞歸實(shí)現(xiàn)，需要一個(gè)等表長(zhǎng)的輔助元素?cái)?shù)組區(qū)間，所以空間復(fù)雜度為O（n）；對(duì)于n個(gè)元素，將這n個(gè)元素看成葉結(jié)點(diǎn)，若將兩兩歸并生成的字表看成他們的父結(jié)點(diǎn)，則歸并過(guò)程對(duì)應(yīng)葉向根生成一顆二叉樹的過(guò)程。所以歸并的趟數(shù)約等于二叉樹的高度，即log2(n),每趟歸并需要移動(dòng)記錄n次，故時(shí)間復(fù)雜度為o(nlog2[n])
閱讀全文