登录
首页 » 算法 » 统计逆序对

统计逆序对

于 2022-01-25 发布 文件大小:233.64 kB
0 212
下载积分: 2 下载次数: 1

代码说明:

资源描述 Description 设a[0…n-1]是一个包含n个数的数组,若在ia[j],则称(i, j)为a数组的一个逆序对(inversion)。 比如 有5个逆序对。请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。 一个n个元素序列的逆序对个数由三部分构成: (1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分元素大于右半部分元素的数量。 其中前两部分(1)和(2)由递归来实现。要保证算法最后效率O(nlogn),第三部分(3)应该如何实现? 此题请勿采用O(n^2)的简单枚举算法来实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中逆序对的个数有关系吗?什么关系? 输入格式 第一行:n,表示接下来要输入n个元素,n不超过10000。 第二行:n个元素序列。 输出格式 逆序对的个数。 输入样例 5 2 3 8 6 1 输出样例 5

下载说明:请别用迅雷下载,失败请重下,重下不扣分!

发表评论

0 个回复

  • 三维张量在不同坐标系的转换可用于昼夜…
    三维张量在不同坐标系统的变换,可用于各向异性介质的介电张量的旋转等问题-3D tensor in different coordinate systems transformation can be used in the dielectric anisotropy tensor rotation problems
    2022-08-15 05:23:31下载
    积分:1
  • leetcode 1 two sum problem
    应用背景leetcode中第一个问题,两个数相加问题。leetcode中第一个问题,两个数相加问题。leetcode中第一个问题,两个数相加问题。leetcode中第一个问题,两个数相加问题。leetcode中第一个问题,两个数相加问题。leetcode中第一个问题,两个数相加问题。leetcode中第一个问题,两个数相加问题。关键技术扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。扫描,然后相加。
    2022-02-05 22:17:56下载
    积分:1
  • BMP Binare 代码,16 系统
    #include < stdlib.h > #include < stdio.h > int (主要) { //ЭТО БУДЕТ ИМЯ ИСХОДНОГО ФАЙЛА char ima_faila [256] ; //БУФЕРНАЯ ПЕРЕМЕННАЯ int 布费尔 ; char prodolzhit_ili_net = "y"; int; chotchik 文件 * f; 请点击左侧文件开始预览 !预览只提供20%的代码片段,完整代码需下载后查看 加载中 侵权举报
    2023-06-14 04:00:04下载
    积分:1
  • SHA-1c 语言实现
    它是一种哈希算法。它用于产生数字签名和指纹图谱的文件或邮件...它采取任意长度的消息和固定长度的摘要 (160) 的生产。
    2022-08-04 00:29:01下载
    积分:1
  • 四叉树---三维场景优化加载 opengl
    三维场景优化加载,用opengl 实现,涉及四叉树分割, LOD  l以及块与块之间裂缝的修补,等等  窥探三维场景四叉树加载的入门例子
    2022-10-25 22:10:02下载
    积分:1
  • 本源码包括矩阵运的基本功能,包括矩阵加减、乘除、转置、求逆...
    本源码包括矩阵运算的基本功能,包括矩阵加减、乘除、转置、求逆-the source of matrix of the basic functions, including matrix addition and subtraction, multiplication and division, to home, the inverse
    2023-02-05 23:15:03下载
    积分:1
  • this is great book for learning elecromagnetic simulation using FDTD
    this great book for learning elecromagnetic simulation using FDTD-this is great book for learning elecromagnetic simulation using FDTD
    2022-01-31 10:37:14下载
    积分:1
  • 牛顿迭代式,用VB实现~~~!
    牛顿迭代式,用VB实现~~~!-Newton iterative, using VB to achieve ~ ~ ~!
    2022-10-16 09:25:03下载
    积分:1
  • 一个求解Josephus问题的函数
      #include #include #define NULL 0 #include typedef struct Lnode {  int data;  struct Lnode *next; }Josephus; void CreateList(Josephus*&L,int n)//建立循环链表 {  int i;  Josephus *p,*s;  s=(Josephus*)malloc(sizeof(Josephus));  s->data=1;  L=p=s;  for(i=2;idata=i;  p->next=s;  p=s;  }  p->next=L; } void DeleteList(Josephus*&L,Josephus*p,Josephus*q) {  q->next=p->next;  free(p); } void Josephus1(Josephus*&L,int s,int m)
    2022-01-27 23:12:59下载
    积分:1
  • 对几个数据进行进行排序的
    工程应用中,往往会涉及到简单的排序算法,尤其是在采样过程中,一般都会先采集一定点的数据,然后进行排序,最终取中间的数据进行平均。
    2023-02-19 15:20:03下载
    积分:1
  • 696516资源总数
  • 106918会员总数
  • 4今日下载