Question

归并排序时间复杂度的递进公式的解是什么?其中O(n)项代表什么

Answer 1

问：归并排序时间复杂度的递进公式的解是什么?其中O(n)项代表什么

答：归并排序时间复杂度的递进公式的解是T(n)=2T(n/2)+o(n).其中O(n)项代表时间复杂度

答：分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度o(1).解决问题时间是两个递归式，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).合并时间复杂度为o（n）。

答：总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。

答：用递归树的方法解递归式T(n)=2T(n/2)+o(n):假设解决最后的子问题用时为常数c，则对于n个待排序记录来说整个问题的规模为cn。