XIAOSUO 记录个人学习的足迹

摘要：什么是跳表 为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。 跳表的时间复杂度 计算跳表的高度 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。 计算跳表的时间复杂度 假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。 跳表的空间复杂度及如何优化 计算索引的节点总数 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的空间复杂度为O(n)。 如何优化时间复杂度 如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。 高效的动态插入和删除 跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O(l…… 阅读全文

摘要：什么是二分查找 二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。 时间复杂度分析 时间复杂度 假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2k)，…，这是一个等比数列。当n/(2k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。 认识O(logn) 这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？ 因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。 由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。 如何实现二分查找 循环实现 func binarySearch1([]int a, val int) int { start := 0 end := len(a) - 1 for start = end { // 不要使用（start + end）/ 2 防止超出边界 mid := start + (end - start) / 2 if a[mid] val { end = mid - 1 } else if a[mid] val { start = mid + 1 } else { return mid } } return -1 } 注意事项： 循环退出条件是：start=end，而不是startend。 mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因为如果start和end比较大的话，求和可能会发生int类型的值超出最大范围。为了把性能优化到极致，可以将除以2转换成位运算，即start + ((end - start) 1)，因为相比除法运算来说，计算机处理位运算要快得多。 start和end的更新：start…… 阅读全文

摘要：一、如何选择合适的排序算法？ 排序算法一览表 时间复杂度 是稳定排序？ 是原地排序？ 冒泡排序 O(n2) 是 是 插入排序 O(n2) 是 是 选择排序 O(n^2) 否 是 快速排序 O(nlogn) 否 是 归并排序 O(nlogn) 是 否 桶排序 O(n) 是 否 计数排序 O(n+k)，k是数据范围 是 否 基数排序 O(dn)，d是纬度 是 否 为什选择快速排序？ 线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。 为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。 同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。 二、如何优化快速排序？ 导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下： 三数取中法 从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。 如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。 随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 警惕快排的递归发生堆栈溢出，有2中解决方法，如下： 限制递归深度，一旦递归超过了设置的阈值就停止递归。 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。 三、通用排序函数实现技巧 数据量不大时，可以采取用时间换空间的思路 数据量大时，优化快排分区点的选择 防止堆栈溢出，可以选择在堆上手动模拟调用栈解决 在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致 四、Go语言排序函数的实现 golang标准库中的Sort用的是快排+希尔排序+插排，数据量大于12时用快排，小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）。其中快排pivot的选择做了很多工作，是基于首中尾中值的很复杂的变种 func quickSort(data Interface, a, b, maxDepth int) { for b-a 12 { …… 阅读全文

摘要：一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。 对排序数据的要求很苛刻，重点掌握此3种排序算法的适用场景。 二、桶排序（Bucket sort） 算法原理： 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 使用条件 要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。 数据在各个桶之间分布是均匀的。 代码实现 func tongSort(values []int) { t := make([]int, 10) for _, val := range values { t[val]++ } res := make([]int, 0, len(values)) for index, val := range t { //循环把排序元素添加到新的数组中 for ; val 0; val-- { res = append(res, index) } } fmt.Println(res) } 适用场景 桶排序比较适合用在外部排序中。 外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。 应用案例 需求描述： 有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序 但内存有限，仅几百MB 解决思路： 扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。 第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。 每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。 将100个小文件依次放入内存并用快排排序。 所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。 注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。 三、计数排序（Counting sort） 算法原理 计数其实就是桶排序的一种特殊情况。 当要排序的n个数据所处范围并不大时，比如最大值为k，则分成k个桶 …… 阅读全文

摘要：一、分治思想 分治思想：分治，顾明思意，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。 分治与递归的区别：分治算法一般都用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。 二、归并排序 算法原理 先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢？写递归代码的技巧就是分写得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。递推公式怎么写？如下 递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件：p = r 不用再继续分解。 代码实现 func mergeSort(arr []int, start, end int) { if start = end { return } mid:=(start + end) / 2 mergeSort(arr, start, mid) mergeSort(arr, mid+1, end) merge(arr, start, mid, end) } func merge(arr []int, start, mid, end int) { var tmparr = []int{} var s1, s2 = start, mid+1 for s1= mid s2= end{ if arr[s1] arr[s2] { tmparr = append(tmparr, arr[s2]) s2++ } else { tmparr = append(tmparr, arr[s1]) s1++ } } if s1=mid { tmparr = append(tmparr, arr[s1: mid+1]...) } if s2=end { tmparr = append(tmparr,…… 阅读全文

摘要：一、排序方法与复杂度归类 几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。 复杂度归类 冒泡排序、插入排序、选择排序 O(n^2) 快速排序、归并排序 O(nlogn) 计数排序、基数排序、桶排序 O(n) 二、算法的执行效率 算法的执行效率 最好、最坏、平均情况时间复杂度。 时间复杂度的系数、常数和低阶。 比较次数，交换（或移动）次数。 排序算法的稳定性 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 稳定性重要性：可针对对象的多种属性进行有优先级的排序。 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。 排序算法的内存损耗 原地排序算法：特指空间复杂度是O(1)的排序算法。 三、冒泡排序 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。 稳定性：冒泡排序是稳定的排序算法。 空间复杂度：冒泡排序是原地排序算法。 时间复杂度： 最好情况（满有序度）：O(n)。 最坏情况（满逆序度）：O(n^2)。 平均情况： “有序度”和“逆序度”：对于一个不完全有序的数组，如4，5，6，3，2，1，有序元素对为3个（4，5），（4，6），（5，6），有序度为3，逆序度为12；对于一个完全有序的数组，如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15，称作满有序度；逆序度=满有序度-有序度；冒泡排序、插入排序交换（或移动）次数=逆序度。 最好情况下初始有序度为n*(n-1)/2，最坏情况下初始有序度为0，则平均初始有序度为n*(n-1)/4，即交换次数为n*(n-1)/4，因交换次数比较次数最坏情况时间复杂度，所以平均时间复杂度为O(n^2)。 func BubbleSort(values []int) { for i := 0; i len(values)-1; i++ { for j := i+1; j len(values); j++ { if v…… 阅读全文

摘要：一、什么是递归？ 递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。 基本上，所有的递归问题都可以用递推公式来表示，比如 f(n) = f(n-1) + 1; f(n) = f(n-1) + f(n-2); f(n)=n*f(n-1); 二、为什么使用递归？递归的优缺点？ 优点：代码的表达力很强，写起来简洁。 缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。 三、递归需要满足的三个条件 问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。 问题与子问题，除了数据规模不同，求解思路完全一样 存在递归终止条件 四、如何实现递归？ 递归代码编写 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 递归代码理解 对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。 那该如何理解递归代码呢？如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。 因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。 五、递归常见问题及解决方案 警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。 警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。 六、如何将递归改写为非递归代码 递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。 比如斐波拉契数列的实现 递归实现 func f(int n) int { if n == 1 { return 1 } if n == 2 { ret…… 阅读全文

摘要：一、什么是队列？ 1.先进者先出，这就是典型的“队列”结构。 2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。 3.所以，和栈一样，队列也是一种操作受限的线性表。 二、如何实现队列 1. 数组实现 type Queue struct { items []interface{} length int //数组大小 head int //表示队头下标 tail int //表示队尾下标 } func CreateStack(cap int) *Queue { if cap == 0 { panic(不能创建容量为0的队列！) } return Queue{ items: [capacity]interface, length: capacity, head:0, tail:0 } } func (this *Queue) Enqueue(item interface{})(err error){ if this.tail == this.length { return errors.New(queue full) } this.items[this.rear] = item this.tail++ return } func (this *Queue) Dequeue() (interface{},err error){ if this.head == this.tail { return _,errors.New(queue empty) } item = this.items[this.head] this.head++ return item,err } 比起栈的数组实现，队列的数组实现稍微有点儿复杂。 对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。 如下图：当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 …… 阅读全文

摘要：如何理解“栈” 栈是一种操作受限的数据结构，只支持入栈和出栈操作。 典型的“栈”结构：后进者先出，先进者后出。 从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。 特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 顺序栈的实现 type Item interface { } type ArrayStack struct { items []Item // 数组 count int //栈中元素个数 size int //栈的大小 } func CreateStack(cap int) *ArrayStack { if cap == 0 { panic(不能创建容量为0的栈！) } return ArrayStack{ items: make([]Item, cap), count: 0, size: cap, } } func (a *ArrayStack) Push(e Item) { if a.size=a.count { panic(栈已经满了！) } a.items[count] = e a.count++ } func (a *ArrayStack) Pop() *Item { if a.count == 0 { panic(栈已经空了！) } tmp = a.items[a.count-1] a.count-- return tmp; } } 链式栈实现 type Item interface { } type StackNode struct { el Item next *StackNode } type ListStack struct { top *StackNode count int //栈中元素个数 } func CreateStack() *ListStack { return new(LinkStack) } func (l *LinkStack) Push(el Item) { s := StackNode{el: el, next: l.top} l.t…… 阅读全文

摘要：什么是链表 和数组一样，链表也是一种线性表。 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。 链表的特点 插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。 常用链表 链表结构五花八门，本文来看一下最常见的三种链表结构，它们分别是：单链表、双向链表和循环链表。 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。 从图中可以发现，其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。 循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。它像一个环一样首尾相连，所以叫作“循环”链表。 双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。 从图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。 插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种…… 阅读全文