数据结构基础
定义
数据结构就是相互之间存在一种或多种特定关系的数据元素的集合
- 举例来说：python自带的基本数据类型list()，由于底层结构是数组，所以不同数据项之间可以互相定位。除此之外，基本没什么其他关系了。但是，如果你基于现有列表的接口（比如append,pop等操作），构建了一个新的数据结构（类），此类构建了几个接口（方法），其中一个可以让每个添加的数据项都能有序的插入到你的结构体中···抽象起来看，就是一个适合做排序相关功能的数据结构。
理解
采用编程语言控制结构和提供的基本数据类型来实现ADT所需要的逻辑接口
数据结构是对ADT的具体实现，同一ADT可以采用不同的数据结构实现
- ADT = Abstract Data Type（抽象数据类型），是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。说白了一个抽象数据类型定义了：一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。至于，一个抽象数据类型到底需要哪些操作，这就只能由设计者根据实际需要来定
- 各种电子设备都拥有“字符串”类型，也需要字符串间的各种操作，那么字符串其实就是一个抽象数据类型，因为在不同的机器上，可能构建原理不同，接口方法不同，但由于其定义的数学特征相同，在计算机编程者看来，它们都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。
两种视角，两种结构
按照视角（使用者和实现者）不同，分为逻辑结构（抽象）和物理结构（实现）
- 逻辑结构可以理解为：为了更方便的解决问题，将数据项之间赋予一定逻辑关系。逻辑结构一般可以可以分为以下4种：集合，线性表，树形，图形
- 物理结构则是数据的逻辑结构在内存中的存储方式，一般有两种，链式存储和顺序存储
数据结构的意义
- 对数据的处理实现"逻辑层"和"物理层"的分离，通过层层的抽象，降低问题解决过程的复杂度，可以定义复杂的数据模型来解决问题，而不需要考虑此模型如何实现
- 好的数据结构应该兼容以前对接口的操作，而在物理实现细节上可以持续改进（程序员不改变逻辑接口使用的前提下，持续优化底层实现方法，而用户专注于调用稳定的接口来解决问题）
生活中的逻辑接口和物理接口（加深理解）
- 汽车有新能源和汽油两种，两种车的设计理念并不相同，比如一种有油箱，一种不需要油箱，一种用电瓶，一种用油箱，虽然物理上的实现不同（比如说油箱和电瓶构造不同，可以说是物理结构不同），但是汽车所有对外提供的接口基本相同，比如说方向盘，都有挡位（可以理解为逻辑接口），都可以通过操作逻辑接口（方向盘，油门等）正常开车，而不需要更改任何驾驶习惯
算法基础
定义
- 算法是逻辑层面上的对于问题的解决，而程序则是物理层面上的对于算法的实现
- 算法是解决特定问题求解步骤的描述，在计算机指令出表现为指令的有限序列
意义
- 算法和数据结构是相辅相成的，没有针对数据结构的算法，光研究数据结构是没有意义的
- 很多经典的数据结构和算法都是计算机界的前辈们总结出来的，通过各种优秀的算法，你能更好的理解数据结构
- 例如：从1到100累加求和，比较来看，方法一就是累加求和，随着数量规模变大，运算时间呈线性增长，而方法二则是高斯前辈提出的累加求和方法，不论数量规模如何变大，运算时间都只是常数级
# 方法一
def sum():
sum = 0
for n in range(1,101):
sum = sum + n
return sum
# 方法二
def sum(n):
return n * (1 + n) / 2
特征
- 输入和输出：数据从哪里来，数据往哪里去
- 有穷性 ：可以在预期的时间内正确的结束程序
- 确定性：每一条指令都有唯一的执行逻辑
- 可行性：每一步都可以通过执行有限的次数完成
好算法的基本要求
- 算法没有逻辑错误，没有语法错误，没有不可预期的错误
- 更少的计算机资源，主要包含两点，更少的存储空间，更快的执行时间
- 对特殊情况以及错误情况有适当的处理程序
算法效率的考量
- 我们说衡量一个算法的好坏，最主要的方面取决于所用空间大小和所用时间长短。
- 因为每个程序员对于同一个问题会提出不同的算法解答，所以时间复杂度的算法必然不能独立于某个程序或是某个算法而言，必须是通用的
- 一般来讲，赋值语句（包含计算或存储的语句）的执行次数应该作为时间复杂度的主要考量因素，而控制流语句仅仅是组织语言的作用
大O表示法
概念及理解
- 算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述，f(n)就是问题规模n的某个函数
- 简单来说，大O表示法就是将程序的所有执行步骤相加，转换为代数项，然后只保留随着（问题规模）n的增加而加速度最快的主导部分
- 大O表示法就是当前最主流的用来衡量算法优差的方法之一
# 举例来说
T（n） = 1 + n
随着n的增大，常数1对于最终的结果几乎没有影响，所以就保留主要增长部分，这里记作时间复杂度为 O（n），称为线性阶
T（n） = n² + n + 3
随着n的增大，常数3和n对于最终的结果影响越来越小，而n²就是增速最快的部分，所以时间复杂度为O（n²），称为平方阶
计算方法
- 常数1取代运行时间中所有的加法常数
- 找到随着n变大，增速最快的步骤，计算复杂度，只保留最高阶项
- 最高阶项存在且不是1，去除与这个项相乘的常数
常用的时间复杂度
1.常数级：O(1)
# O(1)表示该算法的执行时间（或执行时占用空间）总是为一个常量，不论输入的数据集是大是小
print('Hello World')
str = "hello world"
2.对数级：O(log(n))
# O(log2n)表示每次循环，所要处理的数据量减半
# 二分查找
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
if list[mid] == item:
return mid
if list[mid] > item:
high = mid - 1
else:
low = mid + 1
return None
3.线性级：O(n)
# O(N)表示一个算法的性能会随着输入数据的大小变化而线性变化
# 查找元素
def easy_search(list, item):
for index in range(len(list)):
if list[index] == item:
return index
return None
4.线性对数级：O(n*log(n))
# O(nlog2n)表示一个算法的性能会随着输入数据的大小变化而线性对数级变化
# 快速排序
def quick_sort(l):
if len(l) < 2:
return l
else:
pivot = l[0]
less = [i for i in l[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quickSort(less) + [pivot] + quickSort(greater)
5.平方级：O(n²)
O(n2)表示一个算法的性能会随着输入数据的大小变化而发生平方级变化
for i in range(n):
for j in range(n):
print('Hello world')
6.立方级：O(n³)
# O(n3)表示一个算法的性能会随着输入数据的大小变化而发生立法级变化
# 简单的3层for循环嵌套
for i in range(n):
for j in range(n):
for k in range(n):
print('Hello World')
7.指数级：O(2^n)
# O(2^n)表示一个算法的性能将会随着输入数据的每次增加而增大两倍
# 一般用不到这种复杂度
时间复杂度排序
- O(1)<O(log(n)<O(n)<O(n*log(n))<O(n²)<O(n³) < O(2^n)
