前言：本文是用来记录自己学习数据结构与算法的笔记，写的不对的地方欢迎指正。
大O复杂度表示法
表示一种变化趋势，并不是代码的具体执行时间。在公式中通常会忽略掉：常量，低阶，和系数。
复杂度分析
用来分析所写算法的执行时间（时间复杂度）和占用的内存大小（空间复杂度）。
空间复杂度
全称为渐进空间复杂度，用来表示算法的存储空间与数据规模之间的增长关系。
例：
NSMutableArray *arr = [NSMutableArray arrayWithCapacity:n];
for (NSInteger i = 0; i < n; i ++) {
[arr addObject:i];
}
NSLog(@"%@",arr);
这段代码中只有第一行申请了一个大小为n的数组，所以这段代码的空间复杂度为O(n)。
常见的空间复杂度是O(1)，O(n)，O(n²)。
时间复杂度
全称为渐进时间复杂度，用来表示代码执行时间随着数据规模增长的变化趋势。
公式：T(n)=O(f(n))
T(n):代码执行的时间；
f(n):表示每行代码执行的次数总和。
一般去分析一段代码的时间复杂度有几个方法：
1，只关注循环次数最多的一段代码
例：
- (void)exemple:(NSInteger)n
{
NSInteger tmp = 0;//1
for (NSInteger i = 0 ; i < n; i ++) {//2
tmp = tmp + i;//3
}//4
NSLog(@"%ld",tmp);//5
}
上述代码只有第3行执行了n次，其他行都只执行了常数量的次数，所以其时间复杂度为O(n)。
2，总复杂度等于量级最大的那段代码的复杂度
- (void)exemple:(NSInteger)n
{
//1
NSInteger tmp1 = 0;
for (NSInteger i = 0 ; i < 100000; i ++) {
tmp1 = tmp1 + i;
}
NSLog(@"%ld",tmp1);
//2
NSInteger tmp2 = 0;
for (NSInteger i = 0 ; i < n; i ++) {
tmp2 = tmp2 + i;
}
NSLog(@"%ld",tmp2);
//3
NSInteger tmp3 = 0;
for (NSInteger i = 0 ; i < n; i ++) {
for (NSInteger k = 0; k < n; k ++) {
tmp3 = tmp3 + i * k;
}
}
NSLog(@"%ld",tmp3);
}
上述代码1的时间复杂度为O(1)，2的复杂度为O(n)，3的复杂度为O(n²)，所以上述整段代码的时间复杂度为O(n²)。
3，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
- (void)exemple:(NSInteger)n
{
NSInteger tmp = 0;
for (NSInteger i = 0 ; i < n; i ++) {
tmp = [self subExemple:i] + tmp;
}
NSLog(@"%ld",tmp);
}
- (NSInteger)subExemple:(NSInteger)n
{
NSInteger subTmp = 0;
for (NSInteger i = 0 ; i < n; i ++) {
subTmp = subTmp + i;
}
return subTmp;
}
exemple的时间复杂度为O(n)，subExemple的时间复杂度为O(n)，所以这个代码的时间复杂度为O(n*n)=O(n²)。
下面看几个例子：
例1：
- (void)exemple:(NSInteger)n
{
NSInteger tmp = 0;
tmp = tmp * n;
NSLog(@"%ld",tmp);
}
其时间复杂度也是Ο(1)，因为代码中不存在循环语句、递归语句。
例2：
- (void)exemple:(NSInteger)n
{
NSInteger tmp = 1;
while (tmp <= n) {
tmp = tmp * 2;
}
}
代码的执行次数与tmp成某种函数关系。不难看出将所有的tmp值列出，其实就是一个等比数列（1，2，4，8.....）。所以时间复杂度为O(log2n)，又因为大O计数法可以忽略系数，所以最终结果为O(logn)。
例3：
- (void)exemple:(NSInteger)n m:(NSInteger)m
{
NSInteger tmp_n = 0;
for (NSInteger i = 0 ; i < n; i ++) {
tmp_n = tmp_n + i;
}
NSInteger tmp_m = 0;
for (NSInteger i = 0 ; i < n; i ++) {
tmp_m = tmp_m + i;
}
NSLog(@"%ld",tmp_n + tmp_m);
}
我们无法估计m和n的量级关系，所以m和n都不能忽略。那么时间复杂度为O(n+m)。
最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度
要搞明白这三个概念先看一个例子：
//在一个字符串数组里面查找一个字符串，找到就返回对应的下标，假设str一定能在数组中找到
- (NSInteger)exemple:(NSArray *)array str:(NSString *)str
{
NSInteger index = -1;
for (NSInteger i = 0; i < array.count; i ++) {
NSString *tmp = array[i];
if ([tmp isEqualToString:str]) {
index = i;
break;
}
}
return index;
}
最好情况时间复杂度
假设这个字符串就在数组的第一位，那么这个代码只需要执行一次就能获得结果，那么其时间复杂度就是O(1)。
最坏情况时间复杂度
如果这个字符串在数组的最后一位，那么他就需要执行array.count次也就是n次，所以他的时间复杂度是O(n)。
平均情况时间复杂度
不管是最好情况时间复杂度还是最坏情况时间复杂度都是极端的情况，在大多数的时候都不会发生，所以在大多数时候发生的情况就是平均情况时间复杂度。它的计算方法如下：
去掉系数和常数平均情况时间复杂度就是O(n)。
均摊时间复杂度（参考：https://www.jianshu.com/p/b749a8afdfd2）
在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
举例:有一个长度为n的数组,如果数组没满,就往里插入一个数,如果数组满了,就遍历求和。那么绝大多数情况下都是O(1),只有最后一次是O(n),均摊以后就是O(1)。
