【01课_初识算法与数据结构】
一、理解算法
1、算法的概念
算法，个人理解就是计算一段逻辑，最简化，最快速的方式、方法
每个函数，就包含了一定的算法，执行一定的计算逻辑
算法是一系列程序指令，用于解决特定的运算和逻辑问题2、衡量算法好坏的标准
【数据结构】详解时间复杂度和空间复杂度的计算_时间复杂度怎么算-CSDN博客
有时会需要牺牲空间来换取时间，绝大多数情况下，时间复杂度是更重要的，宁可多分配一下空间，也要提升程序的运行速度
1）（渐进）时间复杂度：O
程序运行时间长短。执行的很慢肯定很难受。
时间复杂度是把程序的相对执行时间函数，简化成一个数量级，这个数量级可以是n，n^2，n^3等
3个规则：
1、如果运行时间是常数量级，则用常数1表示
2、只保留时间函数中的最高阶项
3、如果最高阶项存在，就可以省去最高阶项前面的系数
再翻译上面的三个规则：
1、用常数1取代运行时间中的所有加法常数。O（100）=> O（1）
2、在修改后的运行次数函数中，只保留最高阶项。O（N^2+N）=> O（N^2）
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。O（2N^2）=> O（N^2）
时间复杂度算的是执行次数，而不是具体的时间。并不是有多少个循环次数时间复杂度就是多少，得具体分析算法逻辑例如：
1.1）T(n) =3，只有常数量级，转化的时间复杂度就是 T(n) =O(1)
1.2）T(n) =0.5n^2 + 0.5n，最高阶项是0.5n^2，则只保留最高阶0.5n^2，并省去系数0.5,转化的时间复杂度就是 T(n) =O(n^2)
1.3）T(n) =3n ,最高阶项是3n，就可以省去系数3，转化的时间复杂度就是 T(n) =O(n)
1.4）T(n) = 5logn，就可以省去系数5，转化的时间复杂度就是 T(n) =O(logn)
排序：O(1) < O(logn) < O(n) < O(n^2)
2）空间复杂度
程序临时占用存储空间大小，占用空间大，占用有限的计算机资源，其他事干不了了
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，空间复杂度算的是变量的个数2.1）常量空间
算法的存储空间大小固定，和输入规格没有直接关系，空间复杂度记为O(1）
有5个变量，相当于开辟了5个空间，这样一来：O(1)，因为5是常数2.2）线性空间
当算法分配的空间是线性集合，如列表，切集合大小和输入规模n成正比，空间复杂度记为O(n）
我们可以知道准确的空间复杂度有O（N+6) 但实际是O(N)
其中malloc表达的含义是连续开辟了n+1的long long类型的数组。2.3）二维空间
算法分配的空间是一个二维列表组合，且集合的长度和宽度斗鱼输入的规模n成正比，空间复杂度记为O(n^2）
2.4）递归空间
fun(n）>0 ，程序才会执行，达到函数结束条件，即 fun(n）<= 0,递归结束
O(n)
3、算法的应用
1）运算
2）查找
3）排序
4）最优决策
二、理解数据结构
1、数据结构的概念
数据结构是数据的组织、管理和存储格式，目的是更高效地访问和修改数据2、数据结构的类型
1）线性结构
例如：数组、链表、这样的线性结构的物理结构，以及由他们衍生出来的线性结构的逻辑结构：栈、队列等
哈希表
1.1）关于数组
在python语言中，，没有直接使用数组的概念，而是使用列表和元组这两种集合，本质都是对数组的封装。
列表是一个动态可扩展的数组、支持任意的增、删、改元素。列表在内存中的存储方式是顺序存储
而元组是一个不可变的集合，一旦创建，就不再变化。
我们大多用到的是列表对应数组这个概念。
数组适合读操作多，写操作少的场景列表读取 和 更新元素的时间复杂度都是O(n), 因为可以指定元素进行一次操作
数组的插入、删除元素的时间复杂度是O(n)，因为涉及后续元素的移动操作
1.2）关于链表
链表是一种在物理上非连续、非顺序的数据结构，由若干节点所组成。链表在内存中的存储方式是随机存储
单向链表的每一个节点由两部分组成，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next
链表的第一个节点是头结点，最后一个节点是尾节点，尾节点的next指针指向空
与列表的可以随机读取元素不同，对于链表上的元素，我们只能根据前一个节点的指针才能找到下一个节点
如果想让每个节点都能回溯到它的前置节点，可以使用双向链表，具有指向前置节点的prev指针链表的元素的查找，时间复杂度是O(n)，因为要从头节点开始一个个查找
只考虑链表的元素的更新，不考虑之前的查找操作，时间复杂度是O(1)，因为只对那1个节点操作
只考虑链表的插入、删除操作，不考虑之前的查找操作，时间复杂度是O（1），因为只操作1个或者前后2个节点，都是常量
1.3）栈
类似羽毛球的桶，有开着的口和封闭的底部，元素只能先入后出，底部元素所在的位置叫做栈底，顶部元素所在的位置叫做栈顶。栈这种元素，既可用数组实现，也可用链表实现
栈的基本操作就是：入栈、出栈两种
入栈：把新元素放入栈，只允许从栈顶一侧放入元素，新元素的位置会成为新的栈顶
出栈：把元素从栈里取出，只有栈顶元素才能被取出，出栈元素的前一个元素的位置会成为新的栈顶
列表的append方法相当于入栈，pop方法相当于出栈，列表来实现栈
栈，适用于对历史的回溯，
例如实现递归，可以回溯方法的调用链。
最著名的应用场景是面包屑导航，让用户在浏览页面的时候，可以轻松回溯到上一级或者更上一级的页面入栈和出栈都只影响一个元素，不涉及其他元素的移动，时间复杂度都是O（1）
1.4）队列
类似于单行的隧道，先驶入的车辆先出，后驶入的车辆后出，先入先出，必须按照驶入的顺讯进出
队列的操作：入队、出队
队列的出口端叫做队头，是头部元素的位置
队列的入口端叫做队尾，是尾部元素的下一个位置（空着的）
入队：只允许在队尾放入新的元素，新元素的下一个位置将会成为新的队尾
出队：只允许在队头一侧移出元素，出队元素的后一个位置将会成为新的队头
队尾指针指向的位置永远空出一位，所以队列最大容量比数组长度小1
循环队列，利用已出的队元素空出的空间，让队尾指针重新指回数组的首位，在物理存储空间上，队尾的位置也可以在队头之前
队列的应用场景：
队列的输出顺序和输入顺序相同，所以队列通常用于对历史的回放，也就是按照历史重演一遍
例如在多线程中，争夺公平锁的等待队列，就是按照访问顺讯来决定线程在队列中的次序。
再如：网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的
入队和出队的时间复杂度，都是O(1)
特殊的队列
1、双端队列
综合了栈和队列的优点，可以先入先出，也可以先入后出。
从队头一端可以入队或出队，从队尾一端可以入队或出队
2、优先队列
并不遵循先入先出，而是谁的优先级高，谁先出队。
优先队列不属于线性结构了，是基于二叉堆来实现的。1.5）哈希表
哈希表也叫散列表，提供了键和值的映射关系，只要给出一个key，就可以高效查找到它匹配的value,时间复杂度接近O（1）。哈希表也叫散列表，本质上相当于一个数组。在python中，哈希表对应的集合叫做字典。
在面向对象语言中，每个对象都有属于自己的哈希值，无论对象自身的变量类型是什么，他们的哈希值都是一个整数型变量。
哈希表可以说是列表和链表的结合
java中的哈希表采用了链表法，也就是hashMap，python中采用的是开放寻址法，也就是字典，dic
哈希表是两个操作
读：通过给定的key，在哈希表中查找对应的value.先用过哈希函数，把key转化成数组下标，找到数组下标对应的元素
写：在哈希表插入新的键值对，不同的key通过哈希函数获得数组下标，然后在键值对这个实体里存入数组下标对应的位置
哈希表通过哈希函数，实现key和数组下标的转换，通过开发寻址法和链表来解决哈希冲突2）树
例如：二叉树、以及衍生出来的二叉堆
3）图
多对对的关联关系