逆序对

有两种方法理解，但结论都是一样的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)，大部分人都可以推到这一步，其实再展开一下就行了

下面是我手推的

图片说明

全部评论

相关推荐

07-21 22:24
快手_机器学习算法部_机器学习算法工程师(准入职员工)
快手内推
在快手做了三个多月的后端开发实习，在这里浅浅分享下我的实习体验～ 工作节奏: 基本上是早10晚9，周末双休。整体来说工作强度还是不小的，不过应该也是互联网常态了吧QAQ 福利待遇: 技术岗是400/天，晚上8点以后下班会发30餐补，入职也会一次性发180能量券，学校不在当地的话还可以申请1500/月的房补。￥这块老铁厂还是挺大方的哈哈。 实习生培养: 团队氛围很nice，我的mentor人真的很好，有问题向他请教都会很细致很耐心地给我解答，好感度upup～不过同事们平时可能都比较忙，捕捉到他们不容易，所以每次沟通或者汇报前最好提前做好准备。具体工作职责的话，一开始基本是接同事们剩下的活，直接上...
快手公司福利 911人发布
点赞 评论 收藏
分享
07-21 23:06
OPPO_软件开发部_IT开发工程师(准入职员工)
OPPO暑期实习内推
最近好多小伙伴问我在OPPO当管培生咋样，请攻击我最薄弱的地方～ 💼轮岗实践，技能拉满 管培生要在不同岗位轮岗，像我现在在门店，从产品知识、销售技巧到门店运营都得学。和顾客交流，帮他们选到合适的OPPO 设备，成就感拉满！也更懂消费者需求，对以后做策略超有帮助～ 👥大佬带飞，成长特快 公司给配了导师，从业务到职业规划，手把手教。遇到难题，随时能找他们取经，能少走好多弯路！还有各种培训、分享会，行业前沿知识、OPPO 黑科技，听得人热血沸腾，感觉自己在飞速进步～ ✨氛围超棒，青春感十足 OPPO 的小伙伴都很年轻有活力，大家一起头脑风暴、搞活动，像最近推广 Reno14 系列，团队齐心协力，...
OPPO成长空间 507人发布
点赞 评论 收藏
分享
06-09 23:48
贵州大学 Java
点赞 评论 收藏
分享
06-16 11:40
浙江大学
点赞 评论 收藏
分享
昨天 15:24
广西师范大学 大数据开发工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 不卡学历的大厂有哪些？ #
8069次浏览 64人参与
# 百度秋招提前批进度 #
108683次浏览 1151人参与
# 实习如何「偷」产出？ #
14511次浏览 175人参与
# 除了主业以外，你还有哪些其他收入？ #
3213次浏览 56人参与
# 实习打杂，要跑路吗 #
8129次浏览 99人参与
# 风评不好的公司，你会去吗？ #
41257次浏览 274人参与
# 校园里的破防时刻 #
4892次浏览 51人参与
# 职场新人体验 #
9850次浏览 103人参与
# 为什么那么多公司毁约 #
181099次浏览 1339人参与
# 蔚来求职进展汇总 #
92833次浏览 769人参与
# 第一份工作应该选高薪还是热爱？ #
77263次浏览 746人参与
# 一人推荐一个值得去的通信/硬件公司 #
188222次浏览 1867人参与
# 设计人如何选offer #
127422次浏览 748人参与
# 考研可以缓解求职焦虑吗 #
52815次浏览 470人参与
# 学历贬值真的很严重吗？ #
27689次浏览 186人参与
# 腾讯求职进展汇总 #
953610次浏览 9575人参与
# 秋招结束之后的日子 #
77594次浏览 941人参与
# 你觉得现在还能进互联网吗？ #
16587次浏览 178人参与
# 你觉得早上几点上班合适？ #
74417次浏览 308人参与
# 24届软件开发秋招薪资爆料 #
355892次浏览 1229人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务