数据结构第四篇 iOS 数组中的算法分析

根据前几篇和数据结构有关的博客中一些特殊的结构比如栈和队列是用数组来实现的，其中一些操作可能关联到一些复杂度问题，所以根据前几篇的一些例子做一下分析说明。

数组的创建

由于数组创建会有一定的内存保存其内容。当你添加元素到数组的时候，数组后面预留的一部分空间帮你添加元素到数组尾部，当这个数组开始没有足够的空间的时候就会自动分配一个更大的内存空间，然后copy他的元素们到一个新的数组里，这个做法类似之前栈的扩容思路。当然如果数组有足够空间添加元素就是一个O（1）的操作。如果要创建更大的内存，copy元素到新的内存，这个就是O（n）的操作。所以如果你能提前知道或者预估你大概有多少元素在数组里存储，用数组的带有Capacity的初始化方法来初始化，从而避免频繁的创建内存 copy元素造成的性能问题。

数组的添加操作

大部分情况是O（1）复杂度，但是偶尔也有O（n）复杂度。

如果数组还有空间添加元素并且添加到尾部就是大部分的情况，如果数组需要创建更多的空间就是偶尔的情况。如果添加到数组某个随机的位置也是偶尔的情况比如头部或者中间什么位置。

删除数组的元素

删除数组的尾部元素是O（1）复杂度，如果不是尾部例如头部元素或者其他的index的元素就是O（n）

一些数组匹配的操作

containsObject indexOfObject 复杂度O（n），因为里面会有一个遍历的操作。

indexOfObject:inSortedRange:options:usingComparator: 对于这个方法就是使用的二分查找所以复杂度是O(log n)

数组的拷贝操作

里面有一个创建内存并循环的操作 所以是O（n）

具体可以参照微软的一个开源SDK

https://github.com/Microsoft/WinObjC/blob/812d6636036a8d2eaeaaf7b92aa0c7b76252e190/Frameworks/CoreFoundation/Collections.subproj/CFArray.c