1、图灵机

图灵机组成：一条无限长的分格纸带，每格可以记录1个符号一个读写头，可在纸带上左右移动，能读出和擦写格子的字符一个状态寄存器，记录有限状态中的1个状态一系列有限的控制规则：• 某个状态，读入某个字符时：• 要改写成什么字符• 要如何移动读写头• 要改变为什么状态--图灵机规则是一个五元组：[当前状态 || 当前读入的字符 || 要改成什么字符 || 如何移动读写头 || 最后改成什么状态]

2、一般问题分类

--what--面向判断与分类的问题--可以通过有限树状分支对问题进行定位和解决--why--面向求因与证明的问题--基本是从不言自明的公理出发，逐步证明和解释问题--how--面向过程与构建的问题--有穷步骤下解决问题

3、计算复杂型

--可计算：最初只是关注可行性，并不计算具体消耗的时间和空间--计算复杂性主要涉及到：--着重关注具体要花费多少计算步骤或多少存储空间--定义一些衡量指标，对问题的难易程度（所需的执行步骤数/存储空间大小）进行分类，是计算复杂性理论的研究范围--计算复杂性理论研究问题的本质，将各种问题按照其难易程度分类，研究各类问题的难度级别，并不关心解决问题的具体方案--而算法研究的问题：--在不同现实资源约束情况下的不同解决方案，致力于找到效率最高的方案--不可计算问题：--没有解决方案的问题--有解决方案，但是根本无法实现--举例：停机问题   无理数问题

4、程序 = 算法 + 数据结构

--程序设计语言需要为算法的实现提供实现“过程”和“数据”的机制，具体表现为“控制结构”和“数据类型”--程序设计语言均有语句对应控制结构：--顺序处理、分支选择、循环迭代--程序设计语言也提供最基本的数据类型来表示数据，如整数、字符等--但对于复杂的问题而言，直接使用这些基本数据类型不利于算法的表达

5、算法设计

为了控制问题和问题解决过程的复杂度，利用抽象来保持问题的“整体感”而不会陷入到过多的细节中去--过程抽象：--对现实问题进行建模的时候，对算法所要处理的数据，也要保持与问题本身的一致性，不要有太多与问题无关的细节--数据抽象：--“过程抽象”启发我们进行“数据抽象”--相对于程序设计语言中基本数据类型，抽象数据类型（ADT:Abstract Data Type）是对数据进行处理的一种逻辑描述，并不涉及如何实现这些处理--ADT：同一ADT可以采用不同的数据结构来实现，采用程序设计语言的控制结构和基本数据类型来实现ADT所提供的逻辑接口，属于ADT的“物理”层次--比如说：list 插入 删除 排序等  ||  字典 插入 抽取  ||  set集合 去重  这些都是物理层次，二通过这些功能实现某一个逻辑模型是其数据接口的逻辑层次--数据抽象的好处：对数据实现“逻辑”层次和“物理”层次的分离，可以定义复杂的数据模型来解决问题，而不需要立即考虑此模型如何实现Python 数据结构与算法

6、大O数量级：这个概念都讲臭了没啥意思，主要是自己练习着去分析

7、变位词算法

--题目：所谓“变位词”是指两个词之间存在组成字母的重新排列关系如：heart和earth，python和typhon为了简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等--解题思路：解题目标：写一个bool函数，以两个词作为参数，返回这两个词是否变位词--解题方案一：将词1中的字符逐个到词2中检查是否存在存在就“打勾”标记（防止重复检查）如果每个字符都能找到，则两个词是变位词只要有1个字符找不到，就不是变位词数量级为O(n2)--解题方案二：将两个字符串都按照字母顺序排好序再逐个字符对比是否相同，如果相同则是变位词有任何不同就不是变位词数量级是O[nlog(n)]--解题方案三：暴力破解将s1中出现的字符进行全排列，再查看s2是否出现在全排列列表中--解题方案四：对比两个词中每个字母出现的次数，如果26个字母出现的次数都相同的 话，这两个字符串就一定是变位词为每个词设置一个26位的计数器，先检查每个词，在计数器中设定好每个字母出现的次数计数完成后，进入比较阶段，看两个字符串的计数器是否相同，如果相同则输出是变位词的结论

8、python数据结构语言性能

--主要测试python中 list dict 实现各种数据结构的时间效率--总的方案就是，让最常用的操作性能最好，牺牲不太常用的操作80/20准则：80%的功能其使用率只有20%--list :