精选留言（15） NEVER SETTLE 👍（22） 💬（1）温故而知新，学新知识前，一定要复习前面的知识。老师给的图表帮助我梳理了下第一阶段学习的知识。2019-12-16%; 👍（10） 💬（0）👍 现在进入了把书读薄的阶段2019-12-16失火的夏天 👍（6） 💬（0）这是电子版的算法地图总结呀，哈哈2019-12-16空间 👍（5） 💬（0）请问一下为啥数据量太大不能用二分，是因为内存不足吗？2021-09-01道祺 👍（5） 💬（0）精辟，条理清晰。后面打卡可以学学👍2019-12-16Jie 👍（5） 💬（0）正在啃红黑树，谢谢老师分享总结2019-12-16龙光 👍（2） 💬（1）下面这个地方的时间复杂度说的不对，应该是O(n)吧

数组，插入操作，2.在中间第k位插入，时间复杂度O(1)

---

推导过程： 假设数组为arr[n]，即数组的大小是n

当数组中有效数据长度len=i时，有效数据下标的范围是 0~i-1，插入位置k的取值范围是0~i，共(i+1)种情况 当k=0，有1次插入操作，和i次数据移动操作（原0~i-1的数据各向后移动1次），总共i+1次操作 当k=1，有1次插入操作，和i-1次数据移动操作（原1~i-1的数据各向后移动1次），总共i次操作 当k=2，有1次插入操作，和i-2次数据移动操作（原2~i-1的数据各向后移动1次），总共i-1次操作 ...... 当k=i-1，有1次插入操作，和1次数据移动操作（原i-1的数据各向后移动1次），总共2次操作 当k=i，有1次插入操作，总共1次操作 总计操作次数，m=1+2+3+...+(i+1)=(i+1)(i+2)/2 ≈ i^2

所以对于len=i时，共有i+1种情况，总计i^2次操作

i的取值范围是0~n-1 所以总的情况数 = 1+2+3+...+(i+1)+...+n = n(n+1)/2 ≈ n^2 总的操作数 = 1^2+2^2+...+n^2 = n(n+1)(2n+1)/6 ≈ n^3 所以平均复杂度 = n^3 / n^2 = O(n)2023-05-24IV1NINE 👍（2） 💬（0）正好是一个阶段总结，慢慢做题，加油！2020-12-14卖火柴的托儿索 👍（2） 💬（0）对争哥这个总结给满分，太给力了2020-04-26jianhuang_zou 👍（2） 💬（0）点赞👍👍👍2020-04-05北极的大企鹅 👍（1） 💬（0）昨天听了同为学习者的几位的留言和分享 感觉有些时候自己也是那样学的 知道某个阶段也是要硬坚持过去 这不 上午没事的时候就开发实际在编辑器里刷题了2021-03-04他二哥 👍（1） 💬（0）数组的插入操作时间复杂度总结得有问题吧。 2是不要求数组保持原先的顺序吗？和1/3标准不一样，会造成困惑。2020-10-18安排 👍（1） 💬（0）做个记录：基数排序的每一位的范围不能太大，否则就不能用计数排序这种线性排序来排了，也就做不到o(n)的复杂度了。2020-08-03Mirss.zhao 👍（1） 💬（0）很有用，看完之后会发现有的点需要再回头看看文章温习下😂2020-01-01小文 👍（1） 💬（0）我估计我要看几遍才能啃下来 2019-12-25