算法入门Study（一）

一、时间复杂度

1.1 概念

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大的趋势

特点：

1.能够有效评估算法效率。 2.推算方法更简便。 3.存在一定局限性。

1.2 函数渐进界

函数渐进上界（最差时间复杂度）

复杂度由T(n)中最高的项来决定，忽略常数项、T(n)中的各种系数，使用大O记号表示。最实用，因为给出了一个效率安全值。

函数渐进下界（最佳时间复杂度）

用Ω记号表示

平均时间复杂度

体现算法在随机输入数据下的运行效率，用Θ表示

1.3 常见类型

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O (2ⁿ) < O(n!)

常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶

二、空间复杂度

2.1 概念

空间复杂度衡量算法占用内存空间随着数据量变大的增长趋势

算法相关空间：

输入空间：输入数据

暂存空间：暂存数据、栈帧空间、指令空间（统计范围）

输出空间：输出数据（统计范围）

2.2 推算方法

（1）以最差输入数据为准

（2）以算法运行中的峰值内存为准

2.3 常见类型

O(1) < O(logn) < O(n) < O(n²) < O (2ⁿ)

常数阶 < 对数阶 < 线性阶 < 平方阶 < 指数阶

三、数据与链表

3.1 概念

数组是一种线性数据结构，存储数组的内存空间是连续的，而链表的内存空间则无须连续

元素内存地址 = 数组内存地址（首元素） + 元素长度 * 元素索引

索引本质上是内存地址的偏移量

快速排序、归并排序、二分查找等都在数组上进行

在大多数编程语言中，数组的长度是不可变的

3.2 数组插入删除缺点

平均时间复杂度均为O(n)，n为数组长度

超出数组范围的元素会丢失，会造成部分内存空间的浪费

3.3 数组优点与局限性

支持随机访问，且时间复杂度是O(1)

提升后续操作的执行速度

分配连续内存块，无需额外的结构开销

3.4 链表适用性

数组非常大，内存无法提供大的连续空间

每个元素都是一个节点对象，每个节点通过“引用”相连接，引用记录下一个节点的内存地址，使其访问

3.5 链表概念

链表的储存空间是分散的，而不是连续的

链表的组成单位是Node对象，包含两项数据：节点的值和指向下一节点的引用

首个节点被称为“头节点”，最后一个节点为“尾节点”，尾节点指向的是空（None、null、nullptr）

3.6 节点操作

初始化链表—-将头节点当作链表的代称

插入节点—-改变两个节点的引用（指针），时间复杂度为O(1)

删除节点—-改变一个节点的引用（指针）

访问节点—-访问链表的第i个节点需要循环 i - 1轮，时间复杂度为O(n)，效率较低

3.7 常见链表类型

• 单向链表
• 环形链表（首尾相连），任意节点可视为头节点
• 双向链表，朝两个方向遍历链表，需要占用更多的内存空间

总结：

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活拓展
内存效率	占用内存少、浪费部分空间	占用内存多
访问元素	O(1)	O(n)
添加元素	O(n)	O(1)
删除元素	O(n)	O(1)