有一实数序列a1,a2,....an，若iaj，则（ai，aj）形成了一个逆序对，请使用分治算法求整个序列中逆序对个数，并分析算法时间复杂度。
2021-12-19 21:30:43
1KB
1
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数，再求所有元素的逆序数总和，易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数，其时间复杂度为O(nlogn)。
2021-09-27 20:42:46
948KB
1