什么是复杂度？

什么是复杂度？

科技前沿 • 2025-03-28 09:30 • 阅读 39

大家好，我是讯享网，很高兴认识大家。

评估算法优劣的核心指标是什么？

1) 时间复杂度（流程决定） 2) 额外空间复杂度（流程决定）常数项时间（实现细节决定）

常数操作：固定时间

int a 32位 int b 32位 a+b a-b a/b a*b
例：1+1 与+执行时间一样，因为背后都是32位进制的数据进行运算。
寻址：int[] arr[1千万] arr[2千万] arr[8百万] 寻找某一位的数据时间也是一样的，因为是数组是连续的。

复杂度 O(?)

（1）时间复杂度

选择排序：

[0...N-1] 在0...N-1找到最小值放在0位置，在1...N-1找到最小值放在1位置，在2...N-1找到最小值放在2位置，......

0...N-1 看一遍，找到最小值（比较），最小值放在0位置（N次 N-1次比较 1次交换）
1...N-1 看一遍，找到最小值（比较），最小值放在1位置（N-1次 N-2次比较 1次交换）
2...N-1 看一遍，找到最小值（比较），最小值放在2位置（N-2次 N-3次比较 1次交换）......

看+比较： a* $N^{2}$
讯享网+b*N+c （a，b，c常数）

交换：N次

看+比较+交换：a* $N^{2}$ +b*N+c （a，b，c常数）

时间复杂度 O( $N^{2}$ )

public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 找到最小值，在哪，放到0位置上 // 1 ~ n-1 找到最小值，在哪，放到1 位置上 // 2 ~ n-1 找到最小值，在哪，放到2 位置上 for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } }

讯享网

冒泡排序：

0...1、1...2、2...3、 .....、N-2...N-1上谁大谁往后
0...1、1...2、2...3、 .....、N-3...N-2上谁大谁往后
0...1、1...2、2...3、 .....、N-4...N-3上谁大谁往后 ......

时间复杂度 O( $N^{2}$ )

讯享网public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 // 0 ~ N-2 // 0 ~ N-3 for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } } }

插入排序：

分别在0...0、0...1、0...2、0...3、...、0...N-1 上使它们有序

[1 2 3 4 5 6 7] O(N)

[7 6 5 4 3 2 1] O( $N^{2}$ )

public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 不只1个数 for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序 for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } }

（2）额外空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。作为输入参数的空间，不算额外空间。作为输出结果的空间，也不算额外空间。因为这些都是必要的，和现实目标有关的。所以都不算。但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

最优解：先使时间复杂度尽可能的低，再使空间复杂度低

常见的时间复杂度排名从好到差： O(1) O(logN) O(N) O(N*logN) O(N^2) O(N^3) … O(N^K) O(2^N) O(3^N) … O(K^N) O(N!)

相关推荐