admin管理员组文章数量:1130349
题目描述：
Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n numbers a1, ... , an, which we assume are all distinct, and we define an inversion to be a pair i< j such that ai>aj.
We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let’s call a pair a significant inversion if i< j and ai> 2aj. Given an O(nlogn) algorithm to count the number of significant inversions between two orderings.
我的理解：让我们求一个序列的significant inversion个数，这个不同于一般的逆序数，但是求的思想是一样的，都是采用分治法和归并排序的算法实现。但是不同于普通的求逆序数算法，如果是求ai>aj的个数的话，可以在计算合并子序列的逆序数个数的过程中顺便排序。因为如果不满足ai>aj的话，那就将aj放入tmp序列中，继续比较ai和a(j+1)的大小。
在思考多久之后，决定在函数merge的实现中,将计算合并的过程中产生的重要逆序数和给这个合并子序列排序分开用两个while循环实现。具体实现看代码。
#include<iostream>
#include<stdio.h>
#include题目描述：
Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n numbers a1, ... , an, which we assume are all distinct, and we define an inversion to be a pair i< j such that ai>aj.
We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let’s call a pair a significant inversion if i< j and ai> 2aj. Given an O(nlogn) algorithm to count the number of significant inversions between two orderings.
我的理解：让我们求一个序列的significant inversion个数，这个不同于一般的逆序数，但是求的思想是一样的，都是采用分治法和归并排序的算法实现。但是不同于普通的求逆序数算法，如果是求ai>aj的个数的话，可以在计算合并子序列的逆序数个数的过程中顺便排序。因为如果不满足ai>aj的话，那就将aj放入tmp序列中，继续比较ai和a(j+1)的大小。
在思考多久之后，决定在函数merge的实现中,将计算合并的过程中产生的重要逆序数和给这个合并子序列排序分开用两个while循环实现。具体实现看代码。
#include<iostream>
#include<stdio.h>
#include版权声明：本文标题：分治算法题:nlgn时间复杂度计算原序列的重要逆序个数 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://it.en369.cn/jiaocheng/1754939858a2744095.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论