2024.01.20_学习日记

Posted on Edited on In Views:

天气：小雨
学习地点：家
学习时长：6h

学习内容

  1. 认识复杂度和简单排序 基础知识巩固
    1. 一堆数有两个数出现奇数次，其余都是偶数次，怎么找到两个数？这个时候要用到异或，异或就是相同异或为0，不同异或为1，用一个eor把整个数组都异或，最后会得到a^b，这个值找到其中是1的位数，比如第二位是1，那么a和b第二位必然不同，所以用另一个eor去异或数组中第二位是1的数，最后能得到a或者b，然后用之前的eor异或第二个eor，就能得到另一个值。注意：eor & （~eor + 1）就能取出最右侧的1。
    2. O（N^2）的排序：选择、冒泡、插入。其中插入排序会和数据状况有关系，如果本身有序的时候，那就是O（N）的复杂度，但是排序以最差情况估计，所以还是O（N^2）。
    3. 二分法：找局部最小值、找有序数组某个数是否存在、找有序数组的大于某个数的最左侧值等等。
    4. 对数器：不依赖线上测试平台也能搞定是否正确。
    5. 递归的复杂度（master公式）T(N) = aT(N/b) + O(N^d)。b：子过程的样本。a：子过程的计算次数。O(N^d)：子结果合并的时间复杂度。满足如上公式的程序都可以根据master公式计算时间复杂度：log(b，a) > d ：时间复杂度为O(N^log(b，a))。log(b，a) = d ：时间复杂度为O(N^d * logN)。log(b，a) < d ：时间复杂度为O(N^d)
  2. 认识O（N*LogN）排序
    1. 归并排序：方法是左边排序，右边排序，然后merge一下递归。小和问题也可以用归并排序，一个数组，每个位置左边有多少数比当前小，这个可以转化为，右边有多少比当前位置大，然后可以用归并部分找右边有多少比当前大。还有逆序对问题，逆序对就是左边比右边大有多少个对，其实也是归并来解决
    2. 荷兰国旗问题：数组小于等于大于分开，不要求有序。两个区域，一个左一个右，i从左往右，i和左区域边界中间就是等于区域，i位置如果小于5，i和小边界下一个位置交换，小边界往右阔，i往右，如果等于5，i继续往右，如果大于5，i位置和大边界左边交换，大边界左阔，i不动，因为交换后的i还没比较。
    3. 快速排序：随机选一个数（很重要，将n^2降到n*logN），和最后一个值交换，然后以最后一个值做荷兰国旗问题，然后递归。partion返回的是一个数组，就是等于这个值的数组。
    4. 堆排序：heapinsert方法可以把值向上对比形成大根堆，如果一个数组值一开始就知道，变成大根堆结构可以从倒数第二行开始或者从最后一个数开始，往前依次做heapify，也可以形成大根堆（重点优化）。大根堆最大值跟最后一个值交换，然后heapsize-1，让新的堆重新变成大根堆，用heapify操作，就是从头节点跟子节点最大值比，小的话就交换，周而复始就形成大根堆，然后重复交换最大值和最后一个值，最终形成有序。
    5. 小根堆，大根堆：python里堆结构的实现，import heapq，heappush、heappoll方法，适用于小根堆。
    6. 比较器：自定义比较，类似于运算符重载。
  3. 不基于比较的排序（不是很好用，要根据数据状况来看）
    1. 计数排序，统计每个数的词频，然后遍历输出。
    2. 基数排序：根据个位十位百位来排序，放到几个桶里。放到桶里的操作可以用前缀和来代替。这个比较难懂，可以再看看视频。