打卡召集令 | 第一阶段知识总结

NEVER SETTLE

2019-12-16 00:14:47

温故而知新，学新知识前，一定要复习前面的知识。老师给的图表帮助我梳理了下第一阶段学习的知识。

%;

2019-12-16 09:22:14

👍 现在进入了把书读薄的阶段

失火的夏天

2019-12-16 06:43:12

这是电子版的算法地图总结呀，哈哈

空间

2021-09-01 07:01:43

请问一下为啥数据量太大不能用二分，是因为内存不足吗？

道祺

2019-12-16 09:56:10

精辟，条理清晰。后面打卡可以学学👍

Jie

2019-12-16 00:03:17

正在啃红黑树，谢谢老师分享总结

龙光

2023-05-24 23:18:34

下面这个地方的时间复杂度说的不对，应该是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)