算法相关定义

算法

• 解决一类问题
• 具体
• 明确没有歧义

学算法的意义：

• 写好程序提高效率
• 开拓视野增加面试通过率
• 数据可视化、VR、游戏、、AI和现在不知道的Anything

数量级、输入、输出

数量级

其实就是描述多少个零

1.5 * 10：数量级为3，【千】级
淘宝2017年双十一订单量8.12亿：订单数为【亿】级
知乎用户数突破1.6亿：用户数为【亿】级
阿里市值4687亿美金，百度820亿美金：阿里市值领先百度1个数量级
北京人口总数2100万，长沙人口总数791完：北京人口总数比长沙大1个数量级
宇宙中有20万亿亿 - 40万亿亿颗恒星：宇宙恒星数量级为22
Apple市值10047亿美金：苹果市值到达T级

总结：
具体的数组用来记录客观世界
模糊的数字用来理解客观世界

输入和输出

function sum(a) {
    return a.reduce((x, y) => x +y, 0)
}

输入：数组
输出：数字
输入规模：a.length
算法是输入到输出的映射

输入规模

统计淘宝2017年双十一交易额 -> 加和8.12亿订单 -> 统计算法支持【十亿】级的输入

算法设计的客观条件

• 淘宝统计订单的算法应该支持【十亿】级数据，在【毫秒】级时间内完成计算
• 知乎统计用户肖像的算法应该支持【亿】级数据，在【小时】级时间内完成一次统计
• React的VirtualDom应该支持【万】级数据，在【毫秒级】时间内完成一次计算

计算能力的变革

从ENIAC到骁龙CPU，人类的计算能力增长了至少【10万】级倍数（晶体二极管已经塞不进cpu中了，因此2.8G/HZ已经成为时代瓶颈）

一个hadoop分布式集群动辄有数千台机器，【万】级cpu核心，利用分布式算法计算能力达到智能手机的【万】级倍数

量子计算机：50量子比特的量子计算机每秒可以处理1125亿亿次计算。是大数据集群的【亿】级倍数

CPU、寄存器和内存

短期记忆（很少的事情） -> 寄存器（Register）
推理计算 -> 算数逻辑单元（ALU）
长期记忆（很多事情） -> 随机存储器（RAM）
其他：缓存等

时间复杂度

• 一个函数，用大写O表示，比如O(1)、O(n)、O(logN)……
• 定性描述算法的运行时间

O(1)

let i = 0
i += 1

O(n)

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

O(1) + O(n) = O(n)
时间复杂度相加，结果为复杂度高的。因为但n无限大时，O(1)基本可以忽略不计

let i = 0
i += 1
for (let j = 0; j < n; j+=1) {
    console.log(j)
}

O(n) * O(n) = O(n^2)

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        console.log(i, j)
    }
}

O(logN)

let i = 1
while (i < n) {
    console.log(i)
    i *= 2
}

空间复杂度

• 一个函数，用大写O表示，比如O(1)、O(n)、O(n^2)……
• 算法在运行过程中临时占用存储空间大小的量度
  O(1)

let i = 0
i += 1

O(n)

const list = []
for (let i = 0; i < n; i+=1) {
    list.push(i)
}

O(n^2)
时间复杂度相加，结果为复杂度高的。因为但n无限大时，O(1)基本可以忽略不计

const matrix = []
for (let i = 0; i < n; i++) {
    matrix.push([])
    for (let j = 0; j < n; j++) {
        matrix[i].push(j)
    }
}