算法
- 解决一类问题
- 具体
- 明确没有歧义
学算法的意义：
- 写好程序提高效率
- 开拓视野增加面试通过率
- 数据可视化、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)
}
}
网友评论