我的第一篇博客

算法效率

---

• 时间复杂度：

  一般采用大O表示法,

  时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

​ 常见的时间复杂度量级有：

1. 常数阶O(1)

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

上述代码即使有几十几万行，消耗的时间也不会随着某一变量的增长而增长。

2. 对数阶O(logN)

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

while 代码里会循环n-1次，则不妨记x次后 i >=n，即2^x = n,解的 x = log2^n.

3. 线性阶O(n)

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

for 循环内会执行n次，则 消耗的时间会随n的增大而增大。

4. 线性对数阶O(nlogN)

for ( int i = 0 ; i < n;i++ ){
    int x;
    while (x < n){
        x = x * 2;
    }
}

从上述代码中可以看到for循环本身是一个O（n）复杂度，while本身是一个O（log2^n）;

则等价于 for 将 while 循环n次，即n * log2^n.

5. 平方阶O(n²)

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

for 循环内含有个 for 循环，所以即是n*n = n^2.

6. 立方阶O(n³) 、K次方阶O(n^k)

道理与平方阶类似。

7. 指数阶O(2^n)

• 空间复杂度

  空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

  1. 空间复杂度 O(1)

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

  代码中的所有元素所分配的空间都不会随着处理数据的变化而变化，即S(n)=O(1).

  2. 空间复杂度O(n)

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

  这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n).