四.算法

1.什么是算法

​ 它是将输入转换为输出的一系列计算步骤

​ 解决具体问题所需要的解决方法

2.常见的排序算法

直接插入排序

基本思想：将一个记录插入到已排序好的有序表中，从而得到一个新的。即先将序列的第一个记录看成是有序的子序列，然后从第二个序列开始逐个插入，直到整个序列有序为止优点：快、稳定缺点：比较次数越少，插入后数据移动的越多

选择排序

基本思想：从所有序列中先找到最小的，放到第一个位置，然后再看剩余元素中最小的，放到第二个位置…以此类推 完成整个的排序工作优点：数据移动的次数已知（n-1）缺点：比较次数多

冒泡排序

基本思想：在要排序的一组数中，自上而下对相邻的两个数依次进行比较和调整，大数下沉小数上冒优点：稳定缺点：慢，每次只能移动相邻两个数据

3.常见的分类算法

K近邻算法（KNN）

基本思想：计算训练样本和测试样本中每个样本点的距离、对所有的距离值进行排序、选取前K个最小距离的样本、根据这K个样本的标签进行投票，得到最后的分类类别优点：思想简单，既可以用来做分类也能做回归缺点：计算量大、需要大量的内存

朴素贝叶斯

决策树

C4.5

​ 是对ID3算法做了改进：用信息增益率来选择属性，在树构造过程中进行剪枝

4.时间复杂度和空间复杂度

时间复杂度：表示程序运行完成所需要的总时间空间复杂度：是指执行算法所需要的内存空间

5.常见的加密算法

加密算法可以分为：可逆加密和不可逆加密，可逆加密分为对称加密和非对称加密

不可逆加密算法

MD5信息摘要算法

一种被广泛使用的密码散列函数，可以产生一个16字节的散列值，用来确保信息传输完整特点：压缩性（无论数据多长，计算出来的MD5的值长度相同）、由原数据能很容易的计算出MD5的值

对称加密算法

具体算法不是很了解

五.设计模式

1.设计模式的分类

设计模式就是经过前人无数次的实践总结出的，设计过程中可以反复使用的、可以解决特定问题的设计方法

创建型模式：工厂方法，抽象工厂模式、单例模式、建造者模式、原型模式

结构型模式：适配器模式、装饰器模式

行为型模式：策略模式、观察者模式

2.设计模式的六大原则

开闭原则：尽量通过扩展软件实体来解决需求变化，而不是修改已有的代码依赖倒转原则：核心思想是面向接口编程，依赖于抽象而不是具体接口隔离原则：它的意思是使用 多个隔离的接口，比使用单个接口要好单一职责：一个方法，一个类只负责一个职责，每个职责的程序改动不会影响其它程序里氏代换原则：意思是子类可以扩展父类的功能但不能改变父类原有的功能，可以实现父类中的抽象方法迪米特法则：大概意思是已给类要尽量减少对其它对象的依赖，也就是要做到低耦合高内聚

3.单例模式

定义：保证一个类只有一个实例，属于创建型模式

优点：在单例模式中，活动的单例只有一个实体，就能确保所有的对象都访问一个实例；因为系统内存中只存在一 个对象，因此可以节约系统资源

缺点：不适用于变化的对象；由于单例模式中没有抽象层，因此扩展有很大的困难

饿汉模式：类初始化时，会立即加载对象

懒汉模式：类初始化时，不会初始化该对象，只有需要使用的时候 才会创建该对象

应用场景：Windows的任务管理器是典型的单例应用，不能同时打开两个

4.工厂模式

定义：它提供了一种创建对象的最佳方法。在工厂模式里，创建对象时不会对客户端暴露创建逻辑，而是通过使用 一个共同的接口来指向新创建的对象，实现了创建者和调用者分离分类：简单工厂、工厂方法、抽象工厂模式

5.简单工厂模式

定义：定义了一个创建对象的类，由这个类来封装实例化对象的行为，相当于是一个工厂中有各种产品，创建在一个类中，客户不需要知道具体的产品名称，只需要知道

​ 产品 类所对应的参数

缺点：工厂的职责过重，而且当产品类型过多时不利于系统的扩展和维护

应用场景：工厂类负责创建的对象比较少，客户端只知道传入工厂类的参数，对于如何创建对象并不关心

6.工厂方法模式

定义：核心的工厂类不再负责所有产品的创建，而是将具体创建的工作交给子类去做，该核心类成为一个抽象

​ 工厂的角色，仅负责给出具体工厂子类必须实现的接口

应用场景：客户端不知道它所需要的对象的类，抽象工厂类通过其子类来指定创建哪个对象

7.抽象工厂模式

定义：简单地说是工厂的工厂，抽象工厂可以创建具体工厂，由及具体工厂来生产具体产品

应用场景：系统中有多于一个的产品族，而每次只使用其中某一产品族

8.观察者模式

定义：又叫发布-订阅模式。是一种行为型模式，他定义对象之间一种一对多的依赖关系，使得当一个对象改变状态，所有依赖于它的对象都会得到通知并自动更新

职责：主要用于一对多的通知，当一个对象的状态变化时，他需要及时告知一系列对象，令他们做出相应变化

分类：推模型和拉模型

推模型：对象向观察者推送信息，不管观察者是否需要，推送的信息通常都是对象的全部数据

拉模型：对象在通知观察者的时候，只传递少量信息。如果观察者需要更具体的信息，由观察者主动找对象 获取

应用场景：对一个对象状态的更新，需要其他对象同步更新，而且其他对象的数量动态可变，对象仅需要将自己的更新通知给其他对象而不需要知道其他对象的细节