-2403
荣誉版主
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
使用道具 举报
99
不准访问
128
中级农民
243
禁止发言
回复 pcoat 统计个数确实可以nlogn,要输出所有就没办法了。 darksteel 发表于 2011-5-2 08:56
查看全部评分
回复 wwwyhx 有一点。在一次归并中,前半部分的每个元素可以根据其归并后的位置知道后半部分有多少比它小的,这个数是可以O(1)得到的,但如果要把所有都打印出来,那最少还要费那么多次操作。所以统计逆序对数目可以nlogn,但全部打印的话那有多少逆序对复杂度就是多少,而逆序对最多可能有n^2个。 darksteel 发表于 2011-5-2 11:27
本版积分规则 发表回复 回帖后跳转到最后一页