文章目录
- 时间复杂度
- 常数时间的操作
- 时间复杂度的定义
- 时间复杂度的作用
- 剖析递归行为和递归行为时间复杂度的估算
- 排序
- 选择排序
- 冒泡排序
- 插入排序
- 归并排序
- 小和问题
- 问题描述
- 解题思路
- 快速排序
- 荷兰国旗问题
- 问题描述
- 堆排序
- 堆结构
- 大根堆
- 小根堆
- 桶排序
- 二分
- 二分搜索
- ^的运用
- 不用额外空间交换两个数的值
- 数组中存在一个数有奇数次，其他数均出现偶数次，找到那个出现奇数次的数
- 对数器
- 对数器的概念和使用
时间复杂度
常数时间的操作
一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
下面这段代码就是一个常数操作的代码，他仅仅只是从一个数组中取出一个数，跟数组的规模没有任何关系，无论数组是几亿甚至是几十亿也好，执行这段代码所需的时间都不会发生改变。
但下面这段代码不同，下面这段代码是从一个链表中取出对应位置的数（List list = newLinkedList();），在这段代码中拿到对应的值需要先遍历一遍链表，这一操作与链表的规模有关，故链表的规模会影响其执行这段代码的时间。
时间复杂度的定义
时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那么时间复杂度为O(f(N))。
时间复杂度的作用
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。
剖析递归行为和递归行为时间复杂度的估算
用递归方法找一个数组中的最大值，系统上到底是怎么做的？
master公式的使用
T(N) = a*T(N/b) + O(N^d)
- log(b,a) > d -> 复杂度为O(N^log(b,a))
- log(b,a) = d -> 复杂度为O(N^d * logN)
- log(b,a) < d -> 复杂度为O(N^d)
补充阅读:www.gocalf.com/blog/algorithm-complexity-and-master- theorem.html
以下列代码为例
public static int getMax(int[] arr) {
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int L, int R) {
if (L == R) {
return arr[L];
}
int mid = L + ((R - L) >> 1);
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}
在这段代码中 a为2，因为在一次递归中调用了两次process函数 ，b为2，因为在一次递归中将问题的规模缩小为原来的1/2，d为0，因为除去一次递归中除去调用过程外的时间复杂度为O(1)算出d为1
排序
选择排序
选择排序的算法思想是指，将在数组中一开始选定一个数将这个数初始定义为这个数组的最小值，然后遍历这个数组让这个数与数组中所有数进行比较找出真正的最小值并将其与第一个位置交换位置。之后再找到次小值将其与第二个数交换位置，不断重复直到将这个数组的每一个位置都重新赋值。
public static void selectionSort(int[] arr) {
// 数组过滤 （如果数组不存在或数组数组只有一个元素便不需要排序）
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;// 选定一个数
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;//将这个数与数组中的其他数进行比较，找到真正的最小值对应的下标
}
swap(arr, i, minIndex);//将这个下标与对应位置的数交换位置
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
对于其时间复杂度来说 在每找到一个小值时均会进行N-k比较（k表示为已经找到几个小值），这些比较操作均为常数操作则有(n-1)+(n-2)+(n-3)+…1次比较常数操作，n次交换操作，n次赋值操作，由等差数列求和公式可得an^2 +bn+c 次常数操作，则由上文的时间复杂度公式可得：其时间复杂度为 O（n^2）。
注意当两个算法的时间复杂度相同但想要得到这两个算法在运行时间上的优劣时最好采用直接用大数据量跑一遍的方法进行比较而不是用他们进行了多少次常数操作进行比较，因为不同的常数操作虽然每一次所需的时间是相同的但是不同的常数操作之间所需的时间是不同的故最好还是用大数据量跑一遍。
冒泡排序
冒泡排序通过重复遍历要排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。这个过程会重复进行，直到没有再需要交换的元素为止，这意味着数列已经排序完成。
public static void bubbleSort(int[] arr) {
//数组过滤（如果数组不存在或数组数组只有一个元素便不需要排序）
if (arr == null || arr.length < 2) {
return;
}
for (int e = arr.length - 1; e > 0; e--) {
for (int i = 0; i < e; i++) {//遍历数组如果当前数大于其后一个数则这两数交换位置即冒泡
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
插入排序
插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因此它对于小数据量的排序效率很高。
将第一个元素视为已排序序列，从第二个元素开始进行排序。先取出一个待排序的元素，将其与已排序序列中的元素从后向前比较。如果待插入的元素比已排序序列中的某个元素小，则将那个元素向后移动一个位置。
重复这个过程，直到找到一个合适的位置，或者到达已排序序列的开始。后将待排序元素插入到找到的合适位置。
对每一个待排序元素重复步骤，直到所有元素都被插入到已排序序列中。
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
归并排序
归并排序采用分治法（Divide and Conquer）的思想。归并排序将数组分成两半，分别对这两半进行排序，然后将排序好的两部分合并在一起。以下是归并排序的基本思想和步骤：
将数组分成两半，直到每个子数组只有一个元素。一个元素的数组是有序的。
递归地对每个子数组进行归并排序。
将两个有序的子数组合并成一个有序的数组。
合并两个有序数组的基本思想如下：
比较两个子数组的首元素，选择较小的元素放入合并后的数组。
移动选择的元素到下一个位置，继续比较两个子数组的首元素。
重复上述过程，直到一个子数组的所有元素都被合并。
将另一个子数组的剩余元素直接复制到合并后的数组
public static void mergeSort(int[] arr, int[] arrSorted, int left, int right) {
if (left < right) {
// 找到中间索引
int middle = (left + right) / 2;
// 分别对左右两部分进行归并排序
mergeSort(arr, arrSorted, left, middle);
mergeSort(arr, arrSorted, middle + 1, right);
// 合并两个有序数组
merge(arr, arrSorted, left, middle, right);
}
}
// 合并两个有序数组的函数
public static void merge(int[] arr, int[] arrSorted, int left, int middle, int right) {
int i, j, k;
i = left; // 左数组的起始索引
j = middle + 1; // 右数组的起始索引
k = left; // 合并后数组的起始索引
// 合并过程
while (i <= middle && j <= right) {
if (arr[i] < arr[j]) {
arrSorted[k++] = arr[i++];
} else {
arrSorted[k++] = arr[j++];
}
}
// 复制剩余的元素
while (i <= middle) {
arrSorted[k++] = arr[i++];
}
while (j <= right) {
arrSorted[k++] = arr[j++];
}
// 将合并后的数组复制回原数组
for (i = left; i <= right; i++) {
arr[i] = arrSorted[i];
}
}
小和问题
问题描述
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组
的小和。求一个数组 的小和。
例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左
边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、
2; 所以小和为1+1+3+1+1+3+4+2=16
解题思路
小和问题可以看成求一个数右边有多少个数比他大如果比他大便将其自身加入到求小和的过程中，因此这个问题可以用归并排序的算法进行求解，在归并排序的merge阶段对左边界的数进行遍历得到每个数与右边界的数的大小关系，得到右边界的数中有多少数大于左边界对应的数，并将这些数乘积后加入到最后的结果中,并在最后得到结果。
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
public static int mergeSort(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return mergeSort(arr, l, mid)
+ mergeSort(arr, mid + 1, r)
+ merge(arr, l, mid, r);
}
public static int merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
int res = 0;
while (p1 <= m && p2 <= r) {
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ?000000000000 arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
快速排序
荷兰国旗问题
问题描述
将一个数根据一个特定的数划分为小于该数、等于该数、大于该数这三部分
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] <; arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
快速排序便是将这个进行递归 便能排好序
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
堆排序
堆排序算法基于大根堆（最大堆）或小根堆（最小堆）的数据结构。堆排序的基本思想是将无序序列构建成一个堆，然后逐个从堆中取出元素，将其放在序列的末尾，同时重新调整堆，直到堆中只剩下一个元素，此时整个序列就成为了有序序列。
构建最大堆：将无序序列构建成一个最大堆（大根堆）。
交换并重建堆：将堆顶元素（最大值）与序列末尾元素进行交换，然后将序列末尾的元素移除（即缩小堆的大小），并重新调整堆以保持最大堆的性质。
重复交换：重复步骤2，直到堆中只剩下一个元素。
堆结构
大根堆
对于任意一个非叶子节点i（其子节点为2i+1和2i+2，其中索引从0开始），其值总是大于或等于其子节点的值，即：
A[i] >= A[2i+1]
A[i] >= A[2i+2]
其中A是存储堆的数组，且A[0]是根节点。
小根堆
对于任意一个非叶子节点i（其子节点为2i+1和2i+2，其中索引从0开始），其值总是小于或等于其子节点的值，即：
A[i] <= A[2i+1]
A[i] <= A[2i+2]
其中A是存储堆的数组，且A[0]是根节点。
public class HeapSort {
// 堆调整函数，用于调整节点i，确保子树满足最大堆的性质
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点大于根节点，则更新最大值
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点大于当前最大值，则更新最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，交换它们，并继续调整堆
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整被交换节点的子树
heapify(arr, n, largest);
}
}
// 堆排序函数
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个从堆中取出元素并放到数组末尾
for (int i = n - 1; i >= 0; i--) {
// 交换堆顶元素和数组末尾元素
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆
heapify(arr, i, 0);
}
}
}
桶排序
桶排序（Bucket Sort）是一种分布式排序算法，它将数组分为多个桶，每个桶负责排序数组中的一部分数据。桶排序的基本思想是将数据分散到有限数量的桶里，每个桶再分别对各自范围内的数据进行排序，最后依次取出每个桶排序后的数据，从而得到有序的序列。
先根据数据的范围和数据的分布，确定桶的数量。再遍历待排序的数组，将每个元素放入其对应的桶中。通常使用一个函数映射数据到桶的索引。之后对每个桶内的数据使用其他排序算法（如插入排序、快速排序等）进行排序。
最后依次从各个桶中取出数据，并将它们拼接起来，形成有序序列。
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
public static void radixSort(int[] arr, int begin, int end, int digit) {
final int radix = 10;
int i = 0, j = 0;
int[] bucket = new int[end - begin + 1];
for (int d = 1; d <= digit; d++) {
int[] count = new int[radix];
for (i = begin; i <= end; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = end; i >= begin; i--) {
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (i = begin, j = 0; i <= end; i++, j++) {
arr[i] = bucket[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
二分
二分搜索
二分搜索它通过反复将搜索区间一分为二来缩小搜索范围，直到找到目标值或搜索区间为空。
首先，确定要搜索的有序数组的起始索引（通常为0）和结束索引（通常是数组长度减1）。
计算当前搜索区间的中间索引mid，公式为mid = (low + high) / 2。
将中间索引处的元素与目标值进行比较。
如果中间元素等于目标值，则搜索成功，返回中间索引。
如果中间元素大于目标值，则在数组的左半部分继续搜索。
如果中间元素小于目标值，则在数组的右半部分继续搜索。
根据比较结果，更新搜索区间的起始索引或结束索引。
如果中间元素大于目标值，更新high为mid - 1。
如果中间元素小于目标值，更新low为mid + 1。
重复步骤，直到找到目标值或搜索区间为空（即low大于high）。
如果搜索区间为空，说明数组中不存在目标值，返回一个表示失败的标志（通常是-1或其他特定的值）。
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
// 计算中间索引，防止溢出
int mid = low + (high - low) / 2;
// 检查中间元素是否是目标值
if (arr[mid] == target) {
return mid; // 找到目标值，返回索引
}
// 如果中间元素大于目标值，调整搜索区间的高索引
if (arr[mid] > target) {
high = mid - 1;
} else {
// 如果中间元素小于目标值，调整搜索区间的低索引
low = mid + 1;
}
}
// 未找到目标值，返回-1
return -1;
}
^的运用
不用额外空间交换两个数的值
int a=a^b;
int b=a^b;
int a=a^b;
数组中存在一个数有奇数次，其他数均出现偶数次，找到那个出现奇数次的数
以此数组为例
该数组中1出现4次 ，2出现两次，3出现三次
则可用下列这种方法解决。其原理为同一个数异或偶数次后得到的结果一定为0，0异或一个数结果一定为该数，
由于异或操作的结果与顺序无关则上述代码可改成
则两个1异或后为0… 两个2异或后为0 ， 两个3异或后为0,最后结果为0异或3为3，即为数组中出现奇数次的元素。
对数器
对数器的概念和使用
1，有一个你想要测的方法a
2，实现复杂度不好但是容易实现的方法b
3，实现一个随机样本产生器
4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者
方法b
6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
selectionSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
selectionSort(arr);
printArray(arr);
}
