大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;
}