计算量分析 ●若输入文件大小为2k,k为一个整数 Pass0,产生2个run,每个1页 Pass1,产生2k1个run,每个2页 ○Pass2,产生2k2个run,每个4页 ●总共需要og2N+1次pasN为文件的页数, 对每一页做一次读,一次写 ●总共的开销为:2NogN+1)计算量分析 ⚫若输入文件大小为2 k ,k为一个整数 Pass 0，产生2 k个run，每个1页 Pass 1，产生2 k-1个run，每个2页 Pass 2，产生2 k-2个run，每个4页 ⚫总共需要log2N +1次pass,N为文件的页数， 对每一页做一次读，一次写 ⚫总共的开销为：2N*(log2N +1)