时间复杂度

算法时间复杂度应该和事前预估算法时间开销T(n)与问题规模n的关系，可以表示为：

T = T（n）

一般来说算法的时间复杂度只需要考虑阶数高的部分，比如 T = n^2 + 3n + 2，我们可以把它的时间复杂度看成为：T = n^2

如何计算

1. 找到一个基本操作（最深层循环）
2. 分析基本操作的执行次数x与问题规模n的关系 x = f（n）
3. x的数量级O（x）就是算法时间复杂度T（n）

三种复杂度

• 最坏时间复杂度：最坏情况下算法的时间复杂度；
• 平均时间复杂度：所有输入示例等概念出现的情况下，算法的期望运行时间；
• 最好时间复杂度：最坏情况下算法的时间复杂度；

比如：通过顺序索引寻找一个数组中的一个元素，最优算法就是下arr[0] 找到，即将T（n）=O(1) ,而平均时间复杂度为： T（n）=O(n)

例子

void f(int n){
    int i = 1;
    while(i <= n ){
        i = i*2;
        printf("hello");
    }
    printf("hello");
}

分析：总x的循环的次数和i对应的关系为，所以i=x^2,当x^2>n的时候循环结束，即x=lgn+1的时候结束循环，所以时间复杂度T（n）= O（lgn）

空间复杂度

S(n) = O(f(n))

其中n为问题的规模或者大小

导致内存的开销

• 定义的某些变量
• 函数调用

如何计算

对于一般的程序来说：

1. 找到所占空间大小与问题规模相关的变量
2. 分析空间x与问题规模n的关系 x = f(n)
3. x的数量级O（x）就是算法空间复杂度 S(n)

对于用递归的程序来说：

1. 找到递归调用的深度x与问题规模n的关系 x = f(n)
2. x的数量级O（x）就是算法空间复杂度 S(n)