逆序对

有两种方法理解,但结论都是一样的f(n) = 2^(n-3) * n * (n-1),这里只写一种,另一种就是大佬们的组合数学,前面很多人写,这里就不赘述

我们很容易知道f(n)的数值可分为两方面

一:f(n-1)也就是上一个的个数,因为其实就是在n-1的基础上在其前面加0或1,也就说原来的次数就变成了2倍,也就是2*f(n-1)

二:在n-1的前面新加一个1产生的影响,不难发现就是n-1的所有的0的个数,设为g(n-1)

g(n) = n*2^(n-1), 就是所有串1和0的总和除以2.

这里就可以推出来f(n) = g(n-1) + 2*f(n-2),大部分人都可以推到这一步,其实再展开一下就行了

下面是我手推的

图片说明

全部评论

相关推荐

11-19 18:44
已编辑
成都理工大学 Java
程序员花海:我面试过100+校招生,大厂后端面试不看ACM,竞赛经历含金量低于你有几份大厂实习 这个简历整体来看不错 可以海投
如何写一份好简历
点赞 评论 收藏
分享
10-31 22:23
门头沟学院 Java
天然不是卷王:太好了 佬的金九银十结束,等offer吐出来,我的金11银12就要开始了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务