本文主要是一些数据结构与算法书籍的笔记，不对算法做具体深入的研究，时常更新。

复杂度计算

简单理解就是单位花操作时间（操作步数）后，求运行时间的极限表达式

  • 时间复杂度：输入数据与运行时间之间的关系

  • 空间复杂度

哈希函数与哈希表

image-20210409223121834

哈希（Hash）函数和哈希表也成为散列函数和散列表。简单理解，满足以下两个条件的一定程度上可称为哈希函数：

  1. 相同的输入值必定得到相同的输出值；
  2. 能够尽可能的将不同的输入值转换为不同的输出值。

其中第二点被用以评判一个哈希函数的好坏，当哈希函数对不通的输入得到相同的输出时，称之为哈希（散列）冲突。一个好的哈希函数在给定的输入域中很少出现哈希冲突。给出一个函数

function simpleHash(NumArray){
    return NumArray.reduce((a,b)=>a+b);
}

没错就是一个简单的求和，若输入[1,2]始终会得到3，若输入[4,5]将会得到不同的9，满足以上两个条件，可勉强算一个哈希函数。但很明显，除了[1,2]还有[0,3]、[-1,4]等等不同的输入可以得到3，所以说这是一个很糟糕哈希函数。

子串和子序列

算法中的子串和子序列的定义与数学中的定义是一样的。

子序列的定义：某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列；

子串的定义：可以从一个字符串中找到的连续字符串称之为原字符串的子串。

简单理解，子串某种意义上算是子序列，但子序列不一定是字串，abc bcd cde 都属于abcde 的子串，但abd不是abcde的子串而是子序列。

贪心算法

每步都选择局部最优解，最终得到全局最优解。典型问题：

  • 背包问题
  • 集合覆盖问题

衍生出的概念：近似算法，NP完全问题

动态规划

  1. 当一个复杂问题可分解为离散且互相独立的子问题时，便可使用动态规划来解决。
  2. 每种动态规划解决方案都涉及到网格。
  3. 动态规划无法解决子问题互相有依赖的情况。

K最邻近算法

k-nearest neighbours简称KNN，看命名初以为是某个K姓大佬发现的该算法，实际上K大概指的是邻居的数量（了解更多）。

KNN分为分类和回归，分类算法简单描绘为以下三步：

  1. 对某样东西进行分类；
  2. 查找K个最相似（邻近）的分类；
  3. K个相似的分类中，哪个分类数量更多，该样东西便归为此类。

###

相关书籍

  1. 《算法图解》 Aditya Bhargava
  2. 《我的第一本算法书》 石田保辉、宫崎修一
  3. 《学习javascript数据结构与算法》（第2、3版） Loiane Groner