判断以下T(n) = 2T(n/2) + nlogn的时间复杂度是否为Θ(𝑛𝑙𝑜𝑔2𝑛)
时间: 2023-05-28 16:03:37 浏览: 229
根号n段归并排序算法时间复杂度分析过程
不是。
根据主定理,T(n) = 2T(n/2) 的情况属于第二种情况,即a=2, b=2, f(n)=n^1,因为logb(a) = log2(2) = 1,所以f(n) = n^1 = n^logb(a),因此时间复杂度为Θ(nlogn)。并不是Θ(𝑛𝑙𝑜𝑔2𝑛)。
阅读全文
根号n段归并排序算法时间复杂度分析过程