WWDC 拥抱算法 (Embracing Algorithms) 上 _算法

什么是算法？
算法:
在计算或其他解决问题的操作中要遵循的一个或一组规则，特别是通过计算机：一种基本的划分算法。
现在，请假设你正在构建这样一个App：
示例App
你可以选中画布中的某几个图形(view) ，然后对这些图形所在的图层进行多种操作。
比如：将图层向前、向后移动、删除图层等等。
从数组中删除元素
会导致数组越界错误的删除算法
你是否会这样删除数组中的元素呢？ (好吧，很早以前我确实这样写过...... -_-+)
事实上，上面的写法会导致数组越界错误（Fatal error: Index out of range）
为什么？
因为在0..处， for循环的range值就已经确定了。
所以当的元素个数减少时，就会出现索引值超过数组元素容量个数的问题，最终导致越界错误。
不会导致数组越界错误，但是有bug的删除算法
改成while之后，可以避免崩溃问题。因为我们知道while在每次循环开始时，都会去判断循环开始的条件是否成立。
但是，这样做会产生bug ，而且这个bug不容易立刻被发现！
删除两个连续的元素
【WWDC拥抱算法 (Embracing Algorithms) 上】因为每次循环i都会加1 ，所以删除连续的元素中的第一个元素时， i也会加1 。
然而，这一次加1就会导致待删除的连续元素中的第二个元素被跳过。
没有bug ，但是低效的删除算法
更改if部分的逻辑后，可以解决上述问题。
当然，你也可以这样写：
image.png
好像可以完美地完成删除多个元素的任务了。
但是，这个算法的效率(主要考虑时间复杂度)如何呢？
(at:)方法的文档
(at:)方法的时间复杂度
时间复杂度常用大O符号来表示，描述一个函数数量级的渐近上界。
首先，外层for在遍历数组时的时间复杂度是O(n) 。
然后，根据文档可以知道(at:)方法的时间复杂度也是O(n) 。
那么，这个方法整体的时间复杂度就是O(n^2)了！！！ !!!
O(n^2)
如果你的数组有1000、10000个元素，那么。。。结果完全可以想象！
你的程序将会变得很低效！
那么，你现在该怎么办？

文章插图
(where:)方法
(where:)方法的文档
(where:)方法的时间复杂度
这也许就是你想要的， (where:)方法的时间复杂度仅为O(n) ！！！
我们来对比一下不同时间复杂度O(n)和O(n^2)之间的差别：
image.png
你现在一定很好奇(where:)方法内部的算法为什么能够如此高效？
(where:)方法的实现
需要注意的是，这个方法在的扩展中，而且方法被标记为。
所以，待操作的集合一定是可变的！
接下来，看一下(:)的实现，这里才是高效率的关键部分：
(:)的实现
(after:)方法用于改变索引的值，将索引位置向后移动。
显然， (:)方法的复杂度仅为O(n) 。
至此，你也知道了标准库的强大。
所以，可以多花点时间去了解一下Swift。
继续阅读：拥抱算法 ( ) 下
参考文章：