公钥加密系统 在一个公钥加密系统中,任何人参与者都拥有独自的公钥和密钥,通常用P表示公钥,用S表示密钥,公钥用于加密,密钥用于解密.并且公钥可以公开,任何人都可以使用这个公钥发送一段密文,而只有私钥的持有者才可以用私钥解密 公钥和私钥对应的函数互为反函数 {M=P(S(M))M=S(P(M))\left\{ \begin{array}{ll} M=P(S(M)) \\\\ M=S(P(M)...

二叉搜索树的概念 二叉搜索树是一种特殊的二叉树,对于其中的任意结点 x,其左子树中的任何结点的值都小于结点 x 的值,其右子树中的任何结点的值都大于结点 x 的值 二叉搜索树的结点12345struct Node{ int value; Node* lChild; Node* rChild;}; 因此只需要对二叉搜索树进行中序遍历,就可以升序输出所有元素 查询 为了查...

散列表 散列表是一种动态的集合,它支持插入,检索,删除等字典操作.散列表是数组的扩展,一般的数组可以在 O(1) 的时间复杂度内进行随机读取,而散列表则使用一个特殊的函数来为各个元素分组在查找元素,只需要用特殊函数计算一次,就可以知道元素存放的位置 散列表的基本结构是一个关键字数组和链表,任意元素通过哈希函数计算出一个关键字,通过关键字可以直接定位到一个具体链表,然后往链表末尾添加该元素 ...

非线性结构的概念 线性结构是指逻辑上各个结点一一对应的关系,例如链表,即使它在储存上可能并不是顺序储存 非线性结构是指逻辑上存在一对多关系的结点的结构,例如树,图等.它们的任何结点都可能对应着其它多个不同的结点 有根树 二叉树 二叉树在逻辑上是一种树状结构,最顶上的结点被称为根结点,每个结点都有 key, lChild和rChild值,分别记录该结点的值,左子树指针和右子树指针,当k...

串和字符串 串是由零个或多个单独的元素组成的有限长序列. 在计算机中,串的最广泛的用处是字符串,因此一般情况下,串和字符串是等价的,字符串也简称为串,串就是字符串 串的结构 串实际上是一个特殊的数组,它的元素一定是字符类型的,因此他也具有数组所拥有的特性 读取字符串中的一个字符的时间复杂度是O(1),因为可以直接使用地址准确定位,修改字符串当中的一个字符也非常快,但是字符串无法动态地延长...

数组 内存结构 数组是一种顺序存储的结构,他所占用的空间是固定的,不能随意增加或减小,其中所有元素以特定的方式按顺序排列下来,各个元素的位置都是固定的.因此数组是一种有序的线性结构 数组的随机访问性能优秀,因为只需要对首地址进行加减运算就能得到任意位置处的值 123456789101112int a[100];for(int i=0;i<100;i++){ a[i] = i ...

顺序统计量 将长度为nnn的数组升序排序后,则第iii个位置的数字是该数组的第iii小的量,称之为第iii顺序统计量 数组最小值是第1个顺序统计量,最大值是第nnn个顺序统计量,中位数(又称下中位数)是第⌊n+12⌋\left⌊\frac{n+1}{2}\right⌋⌊2n+1​⌋个顺序统计量 ⌊n⌋⌊n⌋⌊n⌋ 表示对nnn向下取整,⌈n⌉\left⌈n\right⌉⌈n⌉表示对nnn...

渐近等价 考虑函数: f(x)=x2+4xf(x)=x^2+4xf(x)=x2+4x 当x→∞x\rightarrow \inftyx→∞时,该函数可以看作x2x^2x2与它的高阶无穷小o(x2)o(x^2)o(x2)之和,即 f(x)=x2+4x=x2+o(x2)f(x)=x^2+4x=x^2+o(x^2) f(x)=x2+4x=x2+o(x2) 于是我们称f(x)f(x)f(x)和x2...

比较排序 顾名思义,比较排序就是通过比较数组里的每个数来排序的算法的统称,经典的比较排序有：冒泡排序,插入排序,快速排序等.它们都是通过逐一比较各个元素,从而得知每个元素应该待的位置. 渐进时间复杂度 为了寻找最佳比较排序算法,我们需要得知比较排序的渐进时间复杂度.但是实际上排序算法通常会受到数组的实际值的影响,因此这里我们先考虑最坏情况. 在一个长度为 n 的数组 A 里,欲得知 A[...

未婚夫问题 假如现在有n个求婚者,被分别标记为1,2,3…N,她们将按顺序被你面试,你每次都必须选择接受或不接受,一旦你接受了其中一个,那么就无法面试后面的人.因此你必须在无法面试后面的人的情况下选出当下最优者. 由于无法预知这些求婚者的平均情况,所以我们必须先面试前k个人,从第k+1个人开始,一旦发现更优者就立即选择她. 关键变量 这个问题中有三个主要的关键变量 最优点x 顾名思义,...