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

统计逆序对

于 2022-01-25 发布 文件大小:233.64 kB
0 141
下载积分: 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 个回复

  • 在MPI上实现的矩阵相乘并行
    在MPI上实现的矩阵相乘并行计算的源程序。- The matrix realizes which on MPI multiplications the parallel computation source program.
    2022-11-09 11:10:04下载
    积分:1
  • k近邻问题,我自己做的,效果有保证,还有测数据
    k近邻问题,我自己做的,效果有保证,还有测数据-k neighbor problem, I do, the effect is guaranteed, as well as measured data
    2023-06-04 05:25:04下载
    积分:1
  • #define 中使用运符 c
    #include < stdio.h > #include < string.h > #define TFTP_TYPE_GET 0 #define TFTP_TYPE_PUT 1 int (主) { printf %("d",TFTP_TYPE_GET) ; }
    2023-06-15 02:11:15下载
    积分:1
  • 振动信号盒维数计
    这是一个一维时间序列计盒维数计算程序,用matlab编写
    2022-06-12 03:22:05下载
    积分:1
  • 数值分析中的分段线性插值问题,程序中含插入点个数输入界面。...
    数值分析中的分段线性插值问题,程序中含插入点个数输入界面。-Numerical Analysis of piecewise linear interpolation, the program containing the insertion point in the number of input interfaces.
    2023-08-25 20:45:02下载
    积分:1
  • 基于图像的数字插入
    资源描述 资源描述 1、本代码写在word文档中,由于保密性等各种原因,需要修改下,需要认真的看 2、本文档的作用是王bmp文件中输入0-9任意组合的数字 3、算法的主要步骤: 1)数字的大小归一化为5*5的大小,然后每个数字都是二值化图像,最后放到一个数组里面,详细请看word文档里的代码 2)然后根据数字插入的位置,将数字插入道图像中
    2022-01-25 22:22:18下载
    积分:1
  • 同时辨识模型阶次和参数的,源自于潘立登的系统建模与辨识。...
    同时辨识模型阶次和参数的算法,源自于潘立登的系统建模与辨识。-At the same time identification model order and parameters of the algorithm, derived from Li-Deng Pan system modeling and identification.
    2023-06-15 16:30:03下载
    积分:1
  • 关于非线性方程和非线性方程组的根的数值和程序!
    关于非线性方程和非线性方程组的根的数值算法和程序!-On the nonlinear equations and nonlinear equations of the numerical algorithm of the root and procedures!
    2022-03-29 10:29:54下载
    积分:1
  • 轻松用c++实现线性选择
    资源描述元素选择问题 给定线性序集中的n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。 当k=1时——找最小元素; 当k=n时——找最大元素; 当k=(n+1)/2——找中位数 算法设计思想 与快速排序算法的设计思想基本相同,即对输入数组进行递归划分,但操作上只对划分出的两个子数组中的一个进行进一步的递归处理;
    2022-01-24 09:05:38下载
    积分:1
  • 塔勒除雾
    基于fattal 的去雾算法修改而来去雾气算法,原始算法来源于  Single image dehazing这篇论文,代码中也附带了这篇论文,做去雾的朋友可以学习下。
    2022-12-11 15:10:04下载
    积分:1
  • 696516资源总数
  • 106409会员总数
  • 8今日下载