-
统计逆序对
资源描述
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
- 2022-01-25 23:20:18下载
- 积分:1
-
辛普森 COMPUETO
辛普森 COMPUETO
- 2022-05-29 07:24:59下载
- 积分:1
-
牛顿迭代法和基于牛顿法的steffensen加速法matlab源代码
资源描述用迭代的方法求解方程的数值解,牛顿迭代法具有二阶收敛度,newton-steffensen法具有三阶收敛度。源代码注释写的很详细,只需要替换掉方程的解析式就可以计算新的方程。
- 2022-03-07 02:11:50下载
- 积分:1
-
bit operation for 64.
bit operation for 64.
- 2022-12-15 05:30:03下载
- 积分:1
-
Bayesian classifier C source code, using IRIS category for example, easily under...
贝叶斯分类器的C++源码,用IRIS作类例子,通俗易懂,适合作模式识别、图像处理研究开发用!-Bayesian classifier C source code, using IRIS category for example, easily understood and suitable for pattern recognition, Image processing research and development with!
- 2022-01-23 10:59:10下载
- 积分:1
-
链表的C++实现
数据结构中的链表的C++的语言实现算法。
和各种实现函数
- 2022-07-17 18:08:19下载
- 积分:1
-
最小二乘法的基本原理和多项式拟合,纯数学讲解,仅供理论学习参考。...
最小二乘法的基本原理和多项式拟合,纯数学讲解,仅供理论学习参考。-The basic principles of least squares and polynomial fitting, pure mathematics to explain, only theoretical study reference.
- 2022-03-05 11:01:29下载
- 积分:1
-
最优化计算方法常用程序集
包括了一维最优化算法 如:0.618法、分数法、二次差值法、三次插值法等源代码
还包括了无约束最优化部分的 共轭梯度法、DFP变尺度法(用导数或者用差分代替导数)、阻尼最小二乘法、鲍威尔法、模式搜索法、单纯性法等程序源代码
其次,约束最优化部分,提供了混合罚函数法(DFP),混合罚函数法(POWELL),综合约束函数双下降法、可变容差法、复合形法、网格法、随机实验法、解线性规划的单纯型法等等方法的源代码。
- 2022-07-08 03:25:11下载
- 积分:1
-
无源蜂鸣器和弦音电路及驱动源码
应用背景公司产品需要用无源蜂鸣器产生和弦音乐,如果单纯产生不同的频率去驱动蜂鸣器,能产生不同音阶的声调,但是没有和弦音的效果,经过查找大量资料,使用电容放电实现拖音的效果,即产生了和弦音,驱动电路及源码如附件关键技术其中BP_PWR 用于控制给电容的充放电,而BUZZER则用于不同音阶的频率的产生,当BP_PWR关掉时,电容开始放电,此时BUZZER仍然有信号输出,直到电容放电完毕后,从电容的放电开始到放电结束,便产生了和弦音,效果很赞的。已经成熟应用于多个公司的产品中。
- 2023-01-28 00:50:04下载
- 积分:1
-
二叉树的中序遍历
二叉树的中序遍历-binary tree which preorder
- 2022-01-30 15:19:38下载
- 积分:1