# 1. 数据结构
- 数据:数据是信息的载体,是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。
- 数据元素:数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。例如,学生记录就是一个数据元素,它由学号、姓名、性别等数据项组成。
- 数据对象:数据对象是具有相同性值的数据元素的集合,是数据的一个子集。
- 数据类型:数据类型是一个值的集合和定义再此集合上的一组操作的总称。
- 原子类型。其值不可再分的数据类型。如bool 和int 类型。
- 结构类型。其值可以再分解为若干成分(分量)的数据类型。
- 抽象数据类型。抽象数据组织及与之相关的操作。
- 数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。]
数据结构分类:
# 2. 算法(Algorithm)
算法是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。
衡量不同算法之间的优劣主要是通过 时间 和 空间 两个维度去考量:
- 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
- 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述
通常会遇到一种情况,时间和空间维度不能够兼顾,需要在两者之间取得一个平衡点是我们需要考虑的。
一个算法通常存在最好、平均、最坏三种情况,我们一般关注的是最坏情况。
最坏情况是算法运行时间的上界,对于某些算法来说,最坏情况出现的比较频繁,也意味着平均情况和最坏情况一样差。
# 2.1 时间复杂度
时间复杂度是指执行这个算法所需要的计算工作量,其复杂度反映了程序执行时间「随输入规模增长而增长的量级」,在很大程度上能很好地反映出算法的优劣与否
一个算法花费的时间与算法中语句的「执行次数成正比」,执行次数越多,花费的时间就越多
算法的复杂度通常用大O符号表述,定义为T(n) = O(f(n))
常见的大O表示形式
符号 | 名称 |
---|---|
O(1) | 常数 |
O(log(n)) | 对数 |
O(n) | 线性 |
O(nlog(n)) | 线性和对数乘积 |
O(n²) | 平方 |
O(2n) | 指数 |
可以看到效率从大到小分别是:O(1)> O(logn)> O(n)> O(nlog(n))> O(n²)> O(2n)
注意的是,算法复杂度只是描述算法的增长趋势,并不能说一个算法一定比另外一个算法高效,如果常数项过大的时候也会导致算法的执行时间变长
时间复杂度的计算:
T(n):函数执行的次数,简化后的估算值,就是时间复杂度
- T(n) = 常数 ----→ O(1)
- T(n) = 常数*n +常数 ----→ O(n) 去掉系数
- T(n) = 常数*$n^5$ +$n^3$ ----→ O($n^5$) 只保留最高次项
# 题目1
# 题目2
# 题目3
# 题目4
# 题目5
# 题目6
# 2.2 空间复杂度
空间复杂度就是算法需要多少内存,占用了多少空间
常用的空间复杂度有 O(1)
、O(n)
、O(n²)
# O(1)
只要不会因为算法里的执行,导致额外的空间增长,就算是一万行,空间复杂度也是 O(1)
,比如下面这样,时间复杂度也是 O(1)
function foo(){
let n = 1
let b = n * 100
if(b === 100){
console.log("开始吃糖")
}
console.log("我吃了1颗糖")
console.log("我吃了2颗糖")
......
console.log("我吃了10000颗糖")
}
2
3
4
5
6
7
8
9
10
11
# O(n)
比如下面这样,n 的数值越大,算法需要分配的空间就需要越多,来存储数组里的值,所以它的空间复杂度就是 O(n)
,时间复杂度也是O(n)
function foo(n){
let arr = []
for( let i = 1; i < n; i++ ) {
arr[i] = i
}
}
2
3
4
5
6
# O(n²)
O(n²)
这种空间复杂度一般出现在比如二维数组,或是矩阵的情况下
就是遍历生成类似这样格式的
let arr = [
[1,2,3,4,5],
[1,2,3,4,5],
[1,2,3,4,5]
]
2
3
4
5