复杂度解说
算法效率
- 算法效率分为两种:工夫效率(工夫复杂度)和空间效率(空间复杂度)
- 它们别离掂量一个算法的运行工夫和所占的空间大小。
工夫复杂度
- 工夫复杂度计算的是一个函数中算法基本操作的执行次数。
- 工夫复杂度针对的是一整个函数。
工夫复杂度的计算方法(大O渐进表示法)
- 大O渐进表示法是一种估算:只取表达式中对后果影响最大的一项。
推导大O阶办法:
- 用数字1取代算数中的所有常数。
- 在批改后的算数中,只保留最高项。
- 如果最高阶存在且不是1,则去除这个项的常数,失去的后果就是大O阶。
例如:
- 下列的工夫复杂度算数为 :F(N) = 2*N + 10
- 所以大O阶表达式为 :O(N)
void Fun1(int N){ int count = 0; for (int i = 0; i < 2 * N; i++) { ++count; } int M = 10; while (M--) { ++count; } printf("%d", count);}
- 留神:当函数中未知数有多个时
例如:
- 工夫复杂度表达式为:F(N) = M + N + 10 时,大O阶为 O(M+N) 或者 O(N)
- 工夫复杂度表达式为:F(N) = 1000 时,大O阶为 O(1) (第一步将所有常数用1代替)
- O(1) 示意的是算法中基本操作执行常数次,而不是真的只执行一次。
- 工夫复杂度表达式为:F(N) = M*M + N + 10 时,大O阶为 O(M^2)
- 工夫复杂度中:为了不便个别把log2N(以2为底数)写作logN (log3N等就不会缩写了)
- 所谓的线性工夫复杂度就是指O(N)。
空间复杂度
- 空间复杂度是对一个算法在运算过程中,长期占用的内存空间大小。
- 空间复杂度不是计算程序占用了多少个字节,而是计算长期变量的个数。
- 空间复杂度的计算方法也采纳大O渐进表示法。
- O(1) 代表常数个变量。
- 递归算法的空间复杂度就是递归的深度乘以每个算法的空间复杂度(每递归一次,就会在栈中创立一个长期的函数)
留神:
- 工夫是累计的,空间是能够复用的
- 创立局部变量后,在程序出大括号后,就会销毁。
程序表和链表
线性表
- 线性表是 n 个具备雷同个性的数据元素的无限序列
- 常见的线性表:程序表、链表、栈、队列等。
- 线性表在逻辑上是线性构造,但理论物理存储上通常是以数组和链式构造的模式存储的。
程序表和链表
程序表:
- 程序表实质就是数组,可能动静增长的,并且外面的数据是间断存储的(从左到右)
- 程序表的逻辑构造和物理构造是统一的,都是间断的。
链表:
- 链表的逻辑构造和物理构造不是统一的
- 物理上内存空间是按需分配,所以不存在空间节约,然而调配的空间是随机的。
- 单链表分为两局部,前一部分用来存储数据,后一部分用来存储指针,指向下一个节点
- 最初一个链表的指针指向NULL。
程序表和链表的比拟
程序表的毛病:
- 程序表动静增容有性能耗费,增容个别是按两倍减少,可能有肯定水平的空间节约。
- 在程序表中插入数据时,须要移动数据,效率较低(O(N))
程序表长处:
- 能够按下标进行随机拜访。
- 程序表的CUP高速缓存命中率比拟高。
- CPU读取数据时,因为CPU的速度远高于内存,所以个别内存中的数据会提前被加载到高速缓存(Cache)中,而后CPU再从Cache中读取数据。
- 然而提前加载数据是按程序缓存的,所以程序表被提前加载时,命中率较高,因为它们的地址是间断的。而链表被提前加载时,因为地址不间断,所以命中率较低。(所谓的命中率就是被提前加载的数据就是CPU刚好须要的数据)
链表的毛病:
- 不反对下标的随机拜访。
- 链表的CPU高速缓存命中率较低,而且可能会造成缓存净化。
链表的长处:
- 按需申请内存,须要存一个数据,就申请一个内存,不存在空间节约。
- 在链表中插入删除数据时,不须要移动数据,效率高。
链表分类
链表分为:
- 单链表带头循环、单链表带头不循环、单链表不带头循环、单链表不带头不循环。
- 双链表带头循环、双链表带头不循环、双链表不带头循环、双链表不带头不循环。
理论中次要应用两种链表
- 无头单向链表:构造简略,个别不会独自用来存储数据,理论中更多的是作为其余数据结构的子结构。
- 带头双向链表:构造最简单,个别独自存储数据。
所谓的带头和不带头:
- 带头链表:是链表在首节点之前设置的一个头节点,然而它不存储无效数据,只是它的指针指向首节点。
- 头结点的作用:是为了不便对链表的操作。保障链表中每个元素都有一个前驱。
单链表定义方法
struct SListNode{ int date; //前一部分存储数据 struct SListNode* next; //后一部分存储下一个节点的指针}
双链表定义方法
struct ListDouble { struct ListDouble* prev; //寄存上一个结点的地址 struct ListDouble* next; //寄存下一个结点的地址 int val;};
栈和队列
栈
- 一种非凡构造的程序表,只容许在一端进行插入和删除元素,进行数据插入和删除的一端称为栈顶,另一端称为栈底。
栈中数据遵循后进先出准则。
队列
- 只容许在一端插入数据,在另一端删除数据。
- 队列遵循先进先出准则。
二叉树
树的概念
- 树是一种非线性的数据结构,它由n个无限节点组成一个具备档次关系的汇合,形态看着像一个倒挂的树。
- 有一个非凡节点,称为根节点,就是第一层的节点,它没有前驱节点。
- 树是递归定义的。
- 节点的度:一个节点含有的子节点个数。
- 叶节点或终端节点:度为0的节点。
- 父节点:一个节点含有子结点,那么这个结点就是根结点的父结点。
- 兄弟结点:雷同父结点的节点。
- 树的度:根结点的度就是树的度。
- 空树的层数为0。
- 森林:多个不相交的树组成的汇合。
二叉树的概念
- 一个节点只能有两个子节点,然而这个两个子节点不肯定都存在。
- 例如:空节点是二叉树,一个节点也是二叉树。
- 对于任何一个二叉树,叶子节点(度为0的节点)永远比度为2的节点多一个。
满二叉树
- 它是一个二叉树,并且每层节点数都达到最大值
- 满二叉树的层数为k,则节点总数为(2^k)-1。
- 每一层都有 2^(n-1) 个节点(也是每层最大节点数)(n是层数)
齐全二叉树
- 齐全二叉树是效率很高的数据结构。
- 齐全二叉树的前k-1层都是满的,最初一层能够不是满的。
- 然而最初一层必须是从左到右顺次排列的。
堆
- 堆在逻辑上是齐全二叉树构造。
- 堆只存在两种类型:大根堆和小根堆。
- 大根堆:父节点的值大于子节点的值。
- 小根堆:父节点的值小于等于子节点的值。
堆的下标法则
- 设父节点下标为 x,右边子节点下标为 y,左边节点下标为 z。
- y = x*2 + 1;
- z = x*2 + 2;
- x = (x - 1)/ 2 或者 (y-1)/ 2;
二叉树的存储
- 二叉树个别用链式构造存储,即用链表来示意一个二叉树。
- 通常办法是:链表中每个节点由三个局部组成,数据域和左右指针。
- 左右指针别离用来指向该节点的左孩子和右孩子,数据域用来存储数据。
- 目前应用的都是二叉链表。
二叉树链式存储的遍历办法
深度优先遍历:
- 前序遍历:先拜访根,而后在拜访左子树,最初拜访右子树。
- 中序遍历:先拜访左子树,而后拜访根,最初拜访右子树。
- 后序遍历:先拜访左子树,而后拜访右子树,最初拜访根。
广度优先遍历:
- 层序遍历:从左到右一层一层的拜访。
排序算法
常见排序算法
- 插入排序:间接插入排序(实用于小量数据)、希尔排序(能够将大的数疾速地挪动都前面,实用于大量数据)
- 抉择排序:抉择排序、堆排序
- 替换排序:冒泡排序、疾速排序(挖坑法、前后指针法)
- 归并排序:归并排序
疾速排序
- 工夫复杂度 O(N * logN)
- 空间复杂度O(logN)
- 稳定性:不稳固
如何取要害数key
- 先取数组的第一个数、最初一个数和两头地位的数,而后取这三个数中不是最大也不是最小的那个数作为key。
- 这种办法能够防止key间接选到最大值或者最小值。
左右指针法快排
- 一前一后两个指针,抉择一个要害数key(个别是结尾位或者末位)
- 如果抉择结尾位为要害数key,则让end向后先走,寻找比key小的数,找到小的数后停下。
- 而后pre向前走,寻找比key大的数,找到后进行。
- 而后替换pre的值和end的值,替换完后,end持续向后挪动。
- 始终循环,直到pre和end相遇为止,相遇时的值肯定是比key小的,所以替换key和pre的值
- 这样,key的数就会被挪动到整个数组的两头值地位,它右边的都比它小,左边的都比它大
- 最初应用递归。
挖坑法快排
- 另外定义一个变量sum,用来保留第一个pre,pre的地位则空进去了。
- 而后end先向前挪动,寻找比sum小的数,找到后将end与pre替换,当初end的地位为空。
- 而后pre向前挪动,寻找比sum大的数,找到将pre与end替换,当初pre的地位为空。
- 而后再是end向前挪动………………
- 这样循环直到pre和end相遇为止,相遇时的地位为空,再将sum的值放到相遇的地位上。
- 这样这个数的右边都是比它小的数,左边都是比它大的数。
- 最初应用递归即可。
前后指针法快排
- 起始地位,pre在第一位,end在第二位。
- 而后end向后挪动,寻找比key小的值,找到后,pre++,而后替换pre和end的值。
- 而后持续end向后挪动,直到end拜访完为止
- 最初在替换pre和key的值
- 这样key这个数的右边都是比它小的数,左边都是比它大的数。
- 最初递归即可。
快排的小区间优化
- 当数据量很大时,在最初几层递归时,会呈现大量递归(呈现大量递归时可能会栈溢出),然而每个递归解决的数据较小。
- 所以为了防止最初几层的递归,在数据量较小时,间接应用插入排序
- 这样大数据处理的最初几层递归,则变为插入排序,能够缩小大量递归,升高解决工夫。
归并排序
- 工夫复杂度O(N * logN)
- 空间复杂度O(N)
- 稳定性:稳固
- 此办法须要借助另外一个长期数组。
- 将数组分为两局部,如果两边都是有序的,那么别离从两局部的起始地位开始比拟,将小的值尾插在新数组中,直到有一部分遍历完为止,再将另一部分剩下的尾插到新数组前面。
- 而后再将排序好的新数组赋值给原数组。
- 如果离开的两局部不是有序的,则别离再次差分,直到最初两局部都有序,执行上述步骤,将其排序。
- 因为判断是否有序比拟麻烦,所以个别不判断是否有序,而是将两局部都当做无序,进而始终拆分,直到最初两局部都只剩下一个数时进行尾插到新数组,而后再赋值给原数组,这样因为都是排序失去的,所以即便是无序的也会变成有序,所以能够不判断是否有序。
- 留神要开释长期数组。
排序算法的稳定性判断
- 数组中雷同的值,排序完后绝对程序不变的就是稳固,反之则为不稳固。