内存是计算机中重要的部件之一，它是外存与CPU进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的，因此内存的性能对计算机的影响非常大。内存(Memory)也被称为内存储器和主存储器，其作用是用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。只要计算机在运行中，CPU就会把需要运算的数据调到内存中进行运算，当运算完成后CPU再将结果传送出来，内存的运行也决定了计算机的稳定运行。 内存条是由内存芯片、电路板、金手指等部分组成的。
对数指数幂运算
一、对数
- 定义
如果a的x次方等于N(a>0且a不等于1)，那么数x叫做以a为底N的对数(logarithm)，记作x=logaN。其中，a叫做对数的底数，N叫做真数。
- 对数运算法则
- 换底公式
二、指数
- 定义
指数是幂运算aⁿ(a≠0)中的一个参数，a为底数，n为指数，指数位于底数的右上角，幂运算表示指数个底数相乘。当n是一个正整数，aⁿ表示n个a连乘。当n=0时，aⁿ=1。
三、幂运算
- 定义
幂运算是一种关于幂的数学运算。同底数幂相乘，底数不变，指数相加。同底数幂相除，底数不变，指数相减。幂的乘方，底数不变，指数相乘。
数据结构四种基本类型
一、集合
- Set = （K,R）其中 K = {1,2,3…} R = {a,b,c…}
- 数据结构中的元素同属一个集合，无其他关系
二、线性结构
- Linearity = （K,R）其中 K = {1,2,3,4,5} R = {<1,3>,<3,5>,<5,2>,<2,4>}
- 数据结构中的元素除第一个外每个元素有且仅有一个直接前驱元素，除最后一个外每个数据元素有且仅有一个直接后继元素
- 常见线性结构：线性表，栈，队列，双队列，数组，串
- 数据结构中的元素存在一对一的关系
三、树形结构
- Tree = (K,R),其中 K = {01,02,03,04,05,06} R = {<01,02>,<01,03>,<02,04>,<02,05>,<03,06>}
- 数据结构中的元素根元素以外每个数据元素有且仅有一个直接前驱元素，可以有多个直接后继元素
- 数据结构中的元素存在一对多的关系
四、图状结构（网状结构）
- Graph =（K,R),其中 K = {01,02,03,04,05} R = {<01,02>,<01,05>,<02,01>,<02,03>,<02,04>,<03,02>,<04,02>,<04,05>,<05,01>,<05,04>}
- 数据结构中的元素可以有多个直接前驱元素，也可以有多个直接后继元素
- 数据结构中的元素存在多对多的关系
时间复杂度和空间复杂度
一、时间复杂度
- 时间复杂度，一般指一个算法的运行时间。
- 常见复杂度
O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n^2)＜O(n^3)＜…＜O(2^n)＜O(n!)
二、空间复杂度
- 空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度。
- 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法的输入输出数据所占用的存储空间、算法在运行过程中临时占用的存储空间这三个方面
迭代和递归
一、递归
- 递归:程序调用自身的编程技巧称为递归,是函数自己调用自己。
- 使用递归要注意的有两点:
- 递归就是在过程或函数里面调用自身
- 在使用递归时,必须有一个明确的递归结束条件,称为递归出口
- 一个问题只要同时满足以下3个条件，就可以用递归来解决:
- 问题的解可以分解为几个子问题的解。何为子问题?就是数据规模更小的问题
- 问题与子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
- 优缺点
- 优点:代码的表达力很强，写起来简洁。
- 缺点:空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。
- 递归代码编写
- 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
二、迭代
- 迭代:用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话,迭代就是A不停的调用B。
三、对比
| 概念 | 优点 | 缺点 |
|---|---|---|
| 递归 | 1.大问题化为小问题,可以极大的减少代码量 2.用有限的语句来定义对象的无限集合 3.代码更简洁清晰，可读性更好 |
1.递归调用函数,浪费空间 2.递归太深容易造成堆栈的溢出 |
| 迭代 | 1.迭代效率高，运行时间只因循环次数增加而增加 2.没什么额外开销，空间上也没有什么增加 |
1.不容易理解 2.代码不如递归简洁 3.编写复杂问题时困难。 |
堆结构
一、概念
- 堆是一种经过排序的树形数据结构，每个节点都有一个值，通常我们所说的堆的数据结构是指二叉树，所以堆在数据结构中通常可以被看做是一棵树的数组对象。
- 堆需要满足以下两个性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值(或者说每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值)
- 堆总是一棵完全二叉树
- 分类
- 最大堆：根节点最大的堆叫做最大堆或大根堆
- 最小堆：根节点最小的堆叫做最小堆或小根堆
- 应用
- 优先队列
- 求中位数
- Top K问题