首先算法和数据结构是分不开的，数据结构是数据的组织方式，算法是数据的操作方式（也就是一组数据的操作方法和操作策略），数据结构是为算法服务的，算法要作用在特定的数据结构之上。

复杂度分析是一种和实际运行环境和实际数据规模无关的数学上的算法评价标准。复杂度分析是衡量数据结构与算法优劣的标准，我们所有的算法都应当放入这个标准下去评判。

复杂度分析

现有一算法用来计算1到n的自然数的和，如下：

// 求和
int sum(int n) {
    int now = 1;
    int sum = 0;
    for(;now <= n; now++){
        sum += now;
    }
    return sum;
}

我们首先要假设每条语句的执行时间是一样的（每条指令的运行时间是一样的），比如int now = 1和sum += now的执行时间都是一个时间单位t，则对于这段程序，其花费的总时间是（3×n + 3) × t，其中now > n; now++;sum+=now大约要执行n次，int now =1；int sum = 0；return sum; 分别要执行一次。

同理我们可以得出下面程序需要花费的总时间是2 × t。

int sum(int i,int j){
    int sum = i+j;
    return sum;
}

也就是说，算法执行的总时间T(n)与每行代码执行的次数f(n)成正比：

T(n) = O( f(n) )

其中n表示数据规模，T(n)表示执行总时间，f(n)表示代码执行的总次数，O表示时间T(n)与执行总次数f(n)的正比关系。

将第一个求和带入公式则表示为：T(n) = O( 3n + 3) , f(n)= 3n+3
将第二个求个带入公式则表示为：T(n) = O( 2) , f(n)=2

这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

数据规模一旦到达某个临界值，公式中的常数、系数与低级部分对增长趋势的影响就可以忽略了。比如下面的代码：int sum =0，int i = 1执行了一次，sum += i执行了n次，sum += j 执行了n × n次。当数据规模很大的时候，算法的绝大多是时间都是花费在执行sum += j这样的代码上面。

int sum(int n){
    int sum = 0;
    for(int i = 1 ; i <= n; i++){
        sum += i;
        for(int j = 1; j<= n ; j++){
            sum += j;
        }
    }
}

所以我们记录大O表示法的时候只需要记录最高阶的数量级就行了，忽略常数，低阶部分和系数。
比如：
第一个例子可以记为：T(n) = O(n)
第二个例子可以记为：T(n) = O(1)
第三个例子可以记为：T(n) = O(n^2)

所以我们在时间分析时间复杂度的时候只需要关注执行次数最多的那段代码就行了，这段代码的时间复杂度就等于整个算法的时间复杂度。比如第一段代码只需要关注，sum+=now；第二段代码只需要关注int sum = i + j；第三段代码只需要关注sum += j。就可以正确分析出时间复杂度。

复杂度加法，总复杂度等于量级最大的那段代码的复杂度：T(n) = max(T1(n) , T2(n)) = max(O1,O2)，也就是取数量级较大的一个作为当前算法的时间复杂度，比如下面代码分别调用了sum两次和sum2一次，T(n) =O(2n + n^2 + 1)，但是cal的时间复杂度依然是有sum2主导，也就意味着它的时间复杂度依然是O(n^2)。

int cal(int n) {
   int sum_1 = sum(n);

   int sum_2 = sum(n);
 
   int sum_3 = sum2(n);
 
   return sum_1 + sum_2 + sum_3;
 }
int sum(int n){
   int result = 0;
   int i = 1;
   // O(n)
   for (; i < n; ++i) {
     result = result + i;
   }
    return result;
}

int sum2(){
    int result= 0;
   int i = 1;
   int j = 1;
   // O(n^2)
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       result = result +  i * j;
     }
   }
}

复杂度乘法，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积：T(n)=T1(n)×T2(n) =O(f(n))×O(g(n))=O(f(n)×g(n))。也就是复杂度的乘积等于数量级规模的乘积。如下面代码：sum函数本身复杂度为n的代码调用了复杂度为n^2 的代码，这使得sum的T(n) = O(n × n^2) = O(n^3)

int sum(int n){
   int result = 0;
   int i = 1;
   // O(n)
   for (; i < n; ++i) {
     int s = sum2(n);
     result = result + i + s;
   }
    return result;
}

int sum2(int n){
   int result= 0;
   int i = 1;
   int j = 1;
   // O(n^2)
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       result = result +  i * j;
     }
   }
}

时间复杂度

常见时间复杂度

O(1) — 常数复杂度
O(log n) — 对数复杂度
O(n) — 线性复杂度
O(n log n) — 对数线性复杂度
O(nᵏ) — 多项式复杂度
O(kⁿ) — 指数复杂度
O(n!) — 阶乘复杂度

通常我们遇不到指数阶复杂度（O(2^n)）和阶乘阶时间复杂度（O(n!)）因为该时间复杂度下的算法通常是用来处理无解问题的。

O(1)时间复杂度是算法性能的极致，通常只会出现在直接计算直接访问的情况下，比如hash直接计算当前元素的数组索引。

O(logn)与O(nlogn)时间复杂度通常是算法性能优化的极限，通常会要我们将O(n^x)的算法优化成(O(n^(x-1) logn))复杂度的算法。这需要在原来算法的基础上应用上合适的算法思想。

O(n^x)时间复杂度通常是我们第一遍实现算法的时候最初能想到的解决方案，它通常是暴力解决问的选项。

O(n+m)和O(n×m)，也就是说算法的复杂度由两个维度影响。这种情况下我们无法知道是数据规模n还是m主导时间复杂度，也就意味着T(n) + T(m) = O(f(n)) + O(f(m))

最好最坏时间复杂度

有如下算法，用来查找数组中有无元素，如果有则返回索引，如果没有则返回-1，如果是中途查到则直接中止查询，返回索引。

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

最好的情况是直接在第一位：时间复杂度是1
最坏的情况是没有这个元素：时间复杂度是n

平均时间复杂度

要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：

(1+2+3+....+n+n)/(n+1) = n(n+3) / 2(n+1)

那么其平均时间复杂度在化简和忽略常数、系数，低阶之后就是O(n)

但是，实际上每种情况发生的概率是不一样的，这里我们假设在每个位置的概率为都是1/n,而元素在数组中的概率为1/2，时间复杂度应当是一个期望时间复杂度，也就是加权平均时间复杂度，即：

1×(1/(2n)) + 2×(1/(2n)) + 3×(1/(2n)) +...+n×(1/(2n)) +  n ×(1/2) = (3n+1)/4 

其结果也是O(n)

均摊时间复杂度

对于一些周期性的特殊情况，我们可以使用摊还分析法计算均摊时间复杂度。比如下面的代码：

 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;

// 这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

每次求和操作都是在n-1次插入操作之后完成的，这也就意味着我们可以将求和操作的时间均摊到前面的n-1次操作之上。而在本次案例上，求和操作的时间复杂度是n，前n-1次操作的总的时间复杂度是n-1，则均摊后的时间复杂度是O( (n + n-1)/ n ) = O(1)。

我们也可是使用平均时间复杂度的方式得出同样的结论，假设需要求和和不需要求和的概率都是1/(n+1) ，每n+1次插入就有一次求和，平均时间复杂度如下：

1 × (1/(n+1)) + 1 × (1/(n+1)) + 1 × (1/(n+1)) +....+ 1 × (1/(n+1)) + n × (1/(n+1)) = O(1)

空间复杂度

通常我们并不关心空间复杂度，一方面是因为内存成本是有限且年年递减的，另一方面是因为算法在运行过程中需要使用的内存是确定的，内存超了程序也跑不起来。
比如上面例子的第一个求和，sum、now、n的内存占用是确定的通常不再有新的内存消耗。即使是递归这样的操作，本质上也是空间换时间的操作，我们的程序也不能一直递归下去，毕竟栈深度有限制，问题的规模也是固定的。
所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。