关于后端:算法与数据结构随笔

工夫复杂度
O(1)：加法减法运算
O(logn)、O(nlogn)：循环中呈现跳阶

i=1;
 while (i <= n)  {i = i * 2;}

O(m+n)、O(m*n)：字符长度运算

浅析最好、最坏、均匀、
均摊工夫复杂度：查找字符串 n，每个字符串呈现的概率为 n

为什么很多编程语言中数组都从 0 开始编号？沿用 c 语言设计
数据内存散布


链表插入

new_node->next = p->next;
p->next = new_node;

队列满状态：(tail+1)%n=head
排序留神点

排序算法的执行效率
排序算法的内存耗费：原地排序或其余
排序算法的稳定性

插入排序：数值比照，最初 j +1 = value


抉择排序

插入排序为什么比冒泡排序好：赋值操作比冒泡排序少

归并排序

// 归并排序算法, A 是数组，n 示意数组大小
merge_sort(A, n) {merge_sort_c(A, 0, n-1)
}
 
// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return
 
  // 取 p 到 r 之间的两头地位 q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

疾速排序：O(nlogn)

// 疾速排序，A 是数组，n 示意数组的大小
quick_sort(A, n) {quick_sort_c(A, 0, n-1)
}
// 疾速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

桶排序（Bucket sort）

基数排序（Radix sort）


无处不在的二分思维

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
 
  while (low <= high) {int mid = (low + high) / 2;
    if (a[mid] == value) {return mid;} else if (a[mid] < value) {low = mid + 1;} else {high = mid - 1;}
  }
 
  return -1;
}

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {high = mid - 1;} else if (a[mid] < value) {low = mid + 1;} else {if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {high = mid - 1;} else if (a[mid] < value) {low = mid + 1;} else {if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}
查找第一个大于等于给定值的元素
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {low = mid + 1;}
  }
  return -1;
}
查找最初一个小于等于给定值的元素
public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {high = mid - 1;} else {if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

跳表：插入、删除操作的工夫复杂度也是 O(logn)


散列抵触：凋谢寻址法、链表法
hash 算法应用场景：平安加密、惟一标识、数据校验、散列函数、负载平衡、数据分片、分布式存储