时间复杂度与数据结构基础

认识大 O 表示法、常见时间复杂度和基础数据结构分类。

1.大O标记法

执行次数函数举例	阶	非正式术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
2n²+2n+1	O(n²)	平方阶
5log n+20	O(logn)	对数阶
6n³+2n²+3n+4	O(n³)	立方阶

2.时间复杂度

O(1)> O(logn)> O(n)> O(n²)> O(n³)

数据结构

1. 定义

数据结构是用来储存、组织数据的方式

2. 数据结构与算法的关系

算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体。

高效的程序需要在数据结构的基础上设计和选择算法

3.数据结构的分类

3.1线性结构

线性结构：一个头一个尾

栈、队列

3.1.1顺序表

顺序表：数据区+信息区


一体式存储：把数据区和信息去存在一起(要求类型一致)
必须整体搬迁，需要较大空间

分离式存储：把数据区和信息区分开存储(因为类型不一致，所以占的字节不同，无法根据字节查找，但地址数据类型一致可以查找)
不需要整体搬迁，数据区和信息区可以分开，比较灵活

顺序表扩容策略：每次扩容固定的容量————拿时间换空间 浪费时间
             每次容量翻倍 ——操作简单 拿空间换时间 可能会出现空间闲置

#顺序表增加元素的三种方式
末尾插入   O(1)
非保序插入 O(1) 插入的两人换位
保序插入   O(n) 后续所有的人位置都要往后移一位

#顺序表删除元素的三种方式
末尾删除   O(1)
非保序删除 O(1) 最后一位补位的两人换位
保序删除   O(n) 后续所有的人位置都要往前一位

3.1.2链表

链表:

3.2非线性结构

非线性结构：多个头多个尾

树、图