算法数据结构笔记 1

2022-05-05 23:40:49

函数的增长量级：

时间复杂度：

问题规模：使用 N 代指关键变量；
big O(N)：一个函数的渐进上界；
big Ω(N)：一个函数的渐近下界；
big Θ(N)：一个函数的渐近紧确界。

时间复杂度不等于实际运行速度，实际运行速度与很多因素有关，如指令本身在内存的存取速度等，要具体分析。

空间复杂度：

O(1)：一般而言，不涉及动态内存分配的空间复杂度都视为常量。

几种排序：

冒号排序 O(N^2)，稳定：

从左到右和下一个数字比较，并挑选较大（小）的数字放在后一个位置，每个 for 循环找到一个最大（小）的数字放在最后，持续执行这个循环 N-1 次。

for(int i = N - 1; i > 0; i--){ //运行长度越来越短
  for(int j = 0; j < i; ++j){
    if(array[j]>array[j+1])
    swap(array, j ,j+1);
  }
};

直接插入排序 O(N^2)，稳定：

不断做到(0~1,2, 3...N-1)范围内的顺序稳定, N从右往左往前比较，并挑选较大（小）的数字放在前一个位置，移动操作类似冒泡排序。

for(int i = 1; i < N; ++i){
  for(int j = i; j >= 0; --j){
    if(array[j-1] > array[j]){
      swap(array, j-1], j);
    }else{
      break;  
    }
  };
};

简单选择排序 O(N^2)，不稳定：

从左到右，每次往后循环，挑选最大（小）的数字放在最前面的位置，持续执行这个循环 N 次。

 for(int i = 0; i < N; ++i){
   int pre_index = i;
   for(int back_index = i + 1; back_index < N; ++back_index){
     pre_index = array[pre_index] < array[back_index] ? pre_index : back_index;
   }
   swap(array, pre_index, index);
 };

位运算：

使用 XOR 交换数字（容易出 BUG）：

A = A ^ B;
B = A ^ B;
A = A ^ B;

优点是节省一个变量，代码简洁，缺点是只有在 A 和 B 不是在一个物理储存区的时候才可以进行此操作，否则可能出现同时为 0 的情况。

XOR 运算的更多应用（开心消消乐）：

XOR 满足交换律、结合律，且两次相同的异或运算结果可以抵消。

假设有数组只有一个数字出现了奇数次，其他数字出现了偶数次的情况，可以使用 0 与所有成员 XOR 运算的方法，求出现了奇数次的数字。
假设有两个奇数次的数字A、B，则求得的为 A⊕B，使用 A⊕B 的最低true位，即 (A⊕B)∧(¬(A⊕B)+1)，将数字归为两类，并分别用 0 做 XOR 运算可求得A、B。

二分查找：

二分查找要求数组存在一定规律。
L+(R-L)/2
master公式

码农公寓