一切都是为了统计代码执行的效率

事后统计法

通过统计、监控，就能得到算法执行的时间和占用的内存大小

大 O 复杂度表示法

随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长

时间复杂度的好坏排序

O(1)（常数阶）< O(logn)（对数阶）< O(n)（线性阶）< O(nlogn)（线性对数阶）< O(n^2)（平方阶）< O(n^3)（立方阶）< O(2^n)（指数阶）< O(n!)（阶乘阶）

常数阶O(1)

 int i = 8;
 int j = 6;
 int sum = i + j;

线性阶O(n)

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

对数阶 O(logn)

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

线性对数阶O(nlogN)

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

O(m+n)、O(m*n)

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

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

  return sum_1 + sum_2;
}

平方阶O(n²)

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

最好最坏复杂度

• 最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度

• 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

空间复杂度

渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系

空间复杂度 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

空间复杂度 O(n)

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

微信公众号

本文链接：