一、何为算法

在计算机程序中通过某种计算方式（如利用某种数据结构、使用某种思维模式）以达到程序计算的目的，此种方式即是算法。

二、算法的意义

如同人生的意义一样，都是在有限的时间、空间内争取最优解！

消耗最少的时间、空间资源，获取最符合预期的效果！

三、如何判定算法最优解

在算法的世界里，存在两个非常重要的概念：时间复杂度和空间复杂度。

时间复杂度： 用于描述一个算法整个执行过程中所消耗的时间。

空间复杂度 用于描述一个算法在执行过程中所占用的存储空间。

一般来说，一个算法的时间复杂度越低，空间复杂度越低，则该算法就是最优的一种解。

但并不是说，时间或者空间某一个维度的值极低视为一个最优解，而是趋近于某种”平衡“状态下，时间复杂度和空间复杂度都可以接受，视为最优解。

四、时间复杂度

时间复杂度全称为渐进时间复杂度，并不是用来描述该算法的实现实际的执行时间，而是一种描述算法执行时间与数据规模之间的增长关系。

使用大OOO表示法来描述时间复杂度，如O(1)O(1)O(1)、O(n)O(n)O(n)、O(n2)O(n^2)O(n2)、O(logn)O(logn)O(logn)、O(log2n)O(log_2n)O(log2n)等

1. O(1)O(1)O(1) 常数阶：

function printN (n) {
  const a = 1;
  const b = 2;
  const c = 3;
  console.log(a + b + c);
}

我们认为无论在函数体中有多少个变量，有多少行，如果没有循环、递归，我们都认为该程序在执行时的时间复杂度都是O(1)O(1)O(1)。

即使有循环、递归，也要看是否和nnn有关系

function printN (n) {
  // 注意这里的是1000，固定值
  for (let i = 0; i < 1000; i++) {
    console.log(i)
  }
}

在这个例子中，不管nnn如何变化，执行时间都是固定的，所以该算法的时间复杂度仍旧是O(1)O(1)O(1)，常数阶。

2. O(n)O(n)O(n) 线性阶：

function printN (n) {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
}
printN(1);
printN(6);
printN(10);

随着nnn的增大，算法的执行时间线性增长。

3. O(n2)O(n^2)O(n2) 平方阶：

function printN (n) {
  for (let a = 0; a < n; a++) {
    for (let b = 0; b < n; b++) {
      console.log(a + b);
    }
  }
}

在该函数执行时，两层循环，消耗时间为n∗n=n2n*n = n^2n∗n=n2，如果是嵌套3层循环，则为n3n^3n3，如果是嵌套k层循环，则为nkn^knk

4. O(logn)O(logn)O(logn) 对数阶：

function prinitN (n) {
  const i = 1;
  while (i <= n) {
    console.log(n);
    i *= 2;
  }
}
printN(8);

在该函数中实际打印的是 ”1 2 4 8" 执行了4次，i的值是持续*2翻倍的。如果使用x表示执行的次数，xxx从000开始，则2x=n2^x = n2x=n，x=log2nx = log_2nx=log2n。xxx是以222为底，nnn的对数。

如果此处是 i *= 3，则x=log3nx = log_3nx=log3n。xxx是以333为底，nnn的对数。

常量忽略原则：

在算法的复杂度中，如果是常量，是可以被忽略不计的。所以就是 O(log2n)=O(log3n)=O(logn)O(log_2n) = O(log_3n) = O(logn)

O(log2n)=O(log3n)=O(logn)。 所以忽略底数，所有对数阶的复杂度都可以记为O(logn)O(logn)O(logn)。

由以上一系列知识，可得如下时间复杂度计算规则。

时间复杂度计算规则

1. 在一个算法中，存在多个复杂度，如O(n)O(n)O(n)、O(n2)O(n^2)O(n2)，存在明确的大小关系，取最大时间复杂度。如果不能明确的确定大小关系，则取二者的复杂度之和；

如O(n2)>O(n)O(n^2) > O(n)O(n2)>O(n)，则该算法的时间复杂度取为O(n2)O(n^2)O(n2)

如存在O(m)O(m)O(m)、O(n)O(n)O(n)、O(k)O(k)O(k)时间复杂度，不能明确mmm、nnn、kkk的大小，则该算法的时间复杂度为 O(m)+O(n)+O(k)O(m) + O(n) + O(k)O(m)+O(n)+O(k)

1. 常数阶复杂度在与其他阶复杂度同时存在时，可以忽略不计；

2. 多层嵌套的时间复杂度为：内外复杂度的乘积；

// 此算法的时间复杂度是多少呢？
function printN (m, n) {
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      console.log(m, n)
    } 
  }
}

此函数算法的时间复杂度为 O(m)∗O(n)O(m) * O(n)O(m)∗O(n)

五、空间复杂度

空间复杂度全称为渐进空间复杂度，同时间复杂度一样，不是描述算法在执行时实际占用的存储空间，而是一种描述算法占用的存储空间与数据规模之间的增长关系。

空间复杂度也是使用大OOO来表示的。

空间复杂度的计算规则也是同时间复杂度是一样的。

1. O(1)O(1)O(1) 常数阶：

function printN (n) {
  const a = 10;
  const b = 10;
  const c = 20;
  console.log(a + b + c);
}

空间复杂度为常数阶，只是声明了几个变量，与nnn的值变化并没有关系，复杂度为O(1)O(1)O(1)

2. O(n)O(n)O(n) 线性阶：

function saveArr (n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
}

变量arr的存储空间长度与nnn是成线性关系增长的

3. O(n2)O(n^2)O(n2) 平方阶：

function saveArr (n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      arr.push(i, j);        
    }
 }
}

变量arr此时为二维数组，空间复杂度为O(n2)O(n^2)O(n2)

六、总结

在今天的文章中，我们初识算法，了解了算法的意义、如何求算法的最优解等。 同时我们掌握了两个非常重要的概念：时间复杂度、空间复杂度，并且知道了如何计算时间复杂度和空间复杂度。

今天是《算法-从菜鸟开始》的开篇，接下来胡哥会和大家一起，针对LeetCode上的经典算法问题，由浅入深，一一深入了解。

算法-从菜鸟开始，而无止境。与君共勉！