旋转数组

题目

定义一个函数，实现数组的旋转。如输入 [1, 2, 3, 4, 5, 6, 7] 和 key = 3， 输出 [5, 6, 7, 1, 2, 3, 4] 考虑时间复杂度和性能

实现思路

思路1

将 k 后面的元素，挨个 pop 然后 unshift 到数组前面

思路2

将 k 后面的所有元素拿出来作为 part1 将 k 前面的所有元素拿出来作为 part2 返回 part1.concat(part2)

写代码

源码和性能测试 array-rotate.js 单元测试 array-rotate.test.js

经过性能测试，知道“思路2”性能更优。看来，思路简单并不一定性能最优。

时间复杂度

复杂度用 O 表示，说的是数量级，而不是具体的数字，如

O(2) O(3) O(100) 其实都是 O(1) O(n) O(2 * n) 其实都是 O(n)

常见的时间复杂度

O(1) 无循环 O(n) 单次循环 O(logn) 二分法 O(n*logn) 单次循环 & 二分法 O(n^2) 嵌套循环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lfghumUa-1689068117268)(./img/时间复杂度.png)]

【注意】如果你用到了 API （如数组 unshift）要结合数据结构去分析复杂度。要看到代码的本质。

空间复杂度

算法需要额外定义多少变量？

O(1) 定义了为数不多的变量，和 n 无关 O(n) 需要定义和 n 级别的变量，如额外复制一个同样的数组 其他不常见

前端算法通常不太考虑空间复杂度，或者它比时间复杂度要次要的多。 因为前端环境，通常内存都是足够的，或者内存不够通常也是其他因素（如媒体文件）。

性能对比

时间复杂度

思路1 - 看代码时间复杂度是 O(n)，但数组是有序结构 unshift 本身就是 O(n) 复杂度，所以实际复杂度是 O(n^2) 思路2 - O(1)。slice 和 concat 不会修改原数组，而数组是有序结构，复杂度是 O(1) 。

空间复杂度

思路1 - O(1) 思路2 - O(n)

答案

整体分析，选择“思路2”

划重点

考虑参数非法情况，代码鲁棒性 算法复杂度 要看到全部的时间复杂度（包括 API） 重时间，轻空间 数组是有序结构，shift unshift 等要慎用 单元测试

扩展 - 不要过度优化

其实还有一种思路，时间复杂度 O(n) ，空间复杂度 O(1) ，思路：

k 前面的元素移动到 i + (length - k) 的位置 k 后面的元素移动到 i - k 的位置

但不推荐这样的做法

前端重时间、轻空间，优先考虑时间复杂度，而非空间复杂度 代码是否易读，是否易沟通 —— 这个比性能更重要！人力成本永远是最贵的！！