数据结构和算法（2）：时间复杂度和空间复杂度
赞
踩
目录
概念
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
为什么要学习算法？
用一个小例子来说明算法的重要性。现在写出一个求1+2+3+……+n结果的程序。
- //实现一
- public int PlusFun1(int n)
- {
- int result = 0; //执行1次
- for (int i = 1; i <= n; i++) //执行n+1次
- {
- result = result + i; //执行n次
- }
- return result; //执行1次
- }//代码共执行2n+3次，并且随着n的增大，执行次数越多；
-
- //实现二
- public int PlusFun2(int n)
- {
- int result = 0;
- result = (1 + n) * n / 2;
- return result;
- }//无论n的大小，代码永远只执行3行
实现一, 执行次数会随着输入n增大而增大。实现二，执行次数无论n的大小，只执行3次。通过上边的例子就可以看出一个好的算法的重要性了吧。好的算法决定了运行效率。
算法的五个特性
-
输入：具有零个或多个输入。
-
输出：至少有一个或多个输出。（算法一定要有输出，没有输出的算法是没有意义的）
-
有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
-
确定性：算法的每一步骤都具有明确的含义；不会出现二义性。
-
可行性：算法的每一步都必须是可行的，每一步都能够通过执行有限次数完成。
算法设计的要求（什么是好的算法）
-
正确性：是指算法至少应该具有输入、输出、和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
-
可读性：算法设计的另一目的是为了便于阅读、理解和交流。
-
健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
-
时间效率高和存储量低（时间复杂度和空间复杂度）
算法效率的度量方法
衡量算法效率的度量方法主要有以下几种：
-
时间复杂度（Time Complexity）：时间复杂度是衡量算法执行时间与输入规模之间关系的指标。它描述了算法所需的操作次数（或指令执行次数）随着输入规模的增长而变化的趋势。时间复杂度通常使用大O记号来表示，如O(1)、O(n)、O(n^2)等。时间复杂度越低，算法的执行时间越短。
-
空间复杂度（Space Complexity）：空间复杂度是衡量算法所需的额外存储空间与输入规模之间关系的指标。它描述了算法所需的额外内存空间随着输入规模的增长而变化的趋势。与时间复杂度类似，空间复杂度也使用大O记号表示，如O(1)、O(n)、O(n^2)等。空间复杂度越低，算法对内存的利用率越高。
我认为最讲的很好的教学视频：
【王道计算机考研 数据结构 - 时间复杂度】
【王道计算机考研 数据结构 - 空间复杂度】 https://www.bilibili.com/video/BV1b7411N798/?p=7&share_source=copy_web&vd_source=38ed12eb64a70618ffa8e44b3d5eadf6
常见的时间复杂度
看完上边的两个视频，相信你已经掌握了时间复杂度和空间复杂。接下来，补充一下常见的时间复杂度的代码示例。通过代码示例更好的理解常见的时间复杂度。
常见的时间复杂度所耗费的时间从小到大一次是：
1.常数阶 O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如:
- Console.Write("Hello World");
- int i = 100;
- i++;
- Console.Write(i);
2.对数阶 O(logn)
-
假设输入规模为 n，算法每次迭代或操作都将问题规模减少一半。例如，二分查找算法在每次迭代中将搜索范围从 n 缩小到 n/2，再缩小到 n/4，以此类推。
-
假设 n 是问题规模，那么整个过程的迭代次数为 x，即 n/2^x = 1，解 x = log(n)。因此，算法的时间复杂度为 O(logn)。
- int i = 1;
- while(i<n)
- {
- i = i * 2;
- }
一些常见的拥有对数阶时间复杂度的算法包括：
- 二分查找（Binary Search）：在有序数组或有序列表中查找目标元素。
- 平衡二叉树（Balanced Binary Tree）的插入和查询操作。
- 分割问题（如快速排序的分割操作）。
- public static int BinarySearch(int[] arr, int target)
- {
- int left = 0;
- int right = arr.Length - 1;
-
- while (left <= right)
- {
- int mid = left + (right - left) / 2;
-
- if (arr[mid] == target)
- return mid;
-
- if (arr[mid] < target)
- left = mid + 1;
- else
- right = mid - 1;
- }
-
- return -1;
- }
3.线性阶 O(n)
假设输入规模为 n，算法需要对每个输入元素进行一次操作。例如，对一个包含 n 个元素的数组进行遍历，算法将对每个元素进行处理。
性阶算法的执行时间随着问题规模的增大而线性增长，这意味着算法的执行时间与输入规模 n 成正比。如果问题的规模翻倍，那么算法的执行时间也会翻倍。
一些常见的具有线性阶时间复杂度的算法包括：
- 线性搜索（Linear Search）：在一个无序列表或数组中搜索目标元素。
- 遍历操作：对数组、链表等数据结构的所有元素进行一次操作。
- 某些简单排序算法的最坏情况时间复杂度，如冒泡排序和插入排序。
- public static bool LinearSearch(int[] arr, int target)
- {
- for (int i = 0; i < arr.Length; i++)
- {
- if (arr[i] == target)
- return true;
- }
-
- return false;
- }
4.nlogn阶 O(nlogn)
该复杂度表示算法的执行时间随着输入规模 n 的增加而以 nlogn 的速度增长。线性对数阶O(nlogN)其实非常容易理解，将时间复杂度为0(logn)的代码循环N遍的话，那么它的时间复杂度就是 n* O(logN)，也就是了O(nlogN)。
- for(m =1; m<n; m++)
- {
- i = 1;
- while( i < n)
- {
- i = i * 2;
- }
- }
一些常见的具有 nlogn 阶时间复杂度的算法包括：
- 归并排序（Merge Sort）：通过分治法将原始数组划分为较小的子数组，并对子数组进行排序，然后再将排好序的子数组进行合并。
- 快速排序（Quick Sort）：通过分治法选择一个基准元素，将原始数组划分为较小和较大的两部分，并对两部分进行递归排序。
- 堆排序（Heap Sort）：使用堆数据结构进行排序，通过构建最大或最小堆来排序数组。
- public static void QuickSort(int[] arr, int left, int right)
- {
- if (left < right)
- {
- int pivotIndex = Partition(arr, left, right);
- QuickSort(arr, left, pivotIndex - 1);
- QuickSort(arr, pivotIndex + 1, right);
- }
- }
-
- private static int Partition(int[] arr, int left, int right)
- {
- int pivot = arr[right];
- int i = left - 1;
-
- for (int j = left; j < right; j++)
- {
- if (arr[j] < pivot)
- {
- i++;
- Swap(arr, i, j);
- }
- }
-
- Swap(arr, i + 1, right);
- return i + 1;
- }
-
- private static void Swap(int[] arr, int i, int j)
- {
- int temp = arr[i];
- arr[i] = arr[j];
- arr[j] = temp;
- }
现在来详细解释快速排序的时间复杂度为O(nlogn)：
-
分割问题：在快速排序中，我们选择一个基准元素（pivot）并根据它将数组分为两个部分，一部分包含小于pivot的元素，另一部分包含大于pivot的元素。这一步骤的时间复杂度是O(n)，因为我们需要遍历整个数组来找到pivot的正确位置。
-
递归处理：接着，我们递归地对两个子数组进行相同的操作，每个子数组的大小约为原数组的一半。因为是递归进行的，每次都会对数组的一半进行处理。
-
递归深度：递归的深度最多是log(n)，这是因为在每一次递归中，数组的大小都会减半，直到处理的数组大小为1。
综合考虑以上因素，快速排序的时间复杂度可以表示为O(n)（分割问题） + O(logn) * O(n)（递归深度 * 递归处理每个子数组） = O(nlogn)。
5.平方阶 O(n^2)
通常，这样的算法会使用两层循环结构，比如嵌套的 for 循环。
一些常见的具有平方阶时间复杂度的算法包括：
- 冒泡排序（Bubble Sort）：通过不断比较相邻元素的大小并进行交换，从而将较大（或较小）的元素逐步移动到数组的一端。
- 选择排序（Selection Sort）：每次从剩余未排序的部分选出最小（或最大）的元素，并将其放置在已排序部分的末尾。
- 插入排序（Insertion Sort）：每次将一个元素插入到已排序部分的适当位置，使得已排序部分保持有序。
- 矩阵乘法（Matrix Multiplication）中的朴素算法：通过遍历矩阵元素并进行乘法和加法运算，计算出两个矩阵的乘积。
- public static void BubbleSort(int[] arr)
- {
- int n = arr.Length;
-
- for (int i = 0; i < n - 1; i++)
- {
- for (int j = 0; j < n - i - 1; j++)
- {
- if (arr[j] > arr[j + 1])
- {
- int temp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = temp;
- }
- }
- }
- }
6.立方阶 O(n^3)
通常，这样的算法会使用三层循环结构，比如嵌套的三个 for 循环。
一些常见的具有立方阶时间复杂度的算法包括：
- 三层嵌套循环的算法：比如计算三维数组或矩阵的元素，或者解决一些需要三个嵌套循环的问题。
- 暴力穷举法：当需要对多个参数进行穷举组合并进行计算时，通常需要使用三层循环来进行全排列或组合的生成。
- public static int CalculateCubeSum(int[,,] cube)
- {
- int sum = 0;
- int n = cube.GetLength(0);
-
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- {
- for (int k = 0; k < n; k++)
- {
- sum += cube[i, j, k];
- }
- }
- }
-
- return sum;
- }
7.指数阶 O(2^n)
对于指数阶时间复杂度O(2^n)的算法，每次问题的规模增加一倍，都会产生两个分支，因此随着问题规模n的增加，产生的递归调用或分支数将呈指数级增长。
- public int Fibonacci(int n)
- {
- if (n <= 0)
- {
- return 0;
- }
- else if (n == 1)
- {
- return 1;
- }
- else
- {
- return Fibonacci(n - 1) + Fibonacci(n - 2);
- }
- }
8.阶乘阶 n!
阶乘:：一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积。特殊地，0的阶乘被定义为1，即0! = 1。
n! = n * (n-1) * (n-2) * … * 3 * 2 * 1
常用阶乘数：
1！=1；
2！=2 * 1 = 2；
3！= 3 * 2 * 1 = 6；
4！= 4 * 3 * 2 * 1= 24;
- static void ProcessFactorial(int n)
- {
- for (int i = 1; i <= Factorial(n); i++)
- {
- // 模拟耗时的操作
- Console.WriteLine($"正在进行第 {i} 次迭代");
- }
- }
-
- static int Factorial(int n)
- {
- if (n < 0)
- {
- throw new ArgumentException("输入的数字不能小于0。");
- }
-
- if (n == 0 || n == 1)
- {
- return 1;
- }
-
- return n * Factorial(n - 1);
- }
空间复杂度的补充
空间复杂度是算法分析中用来评估算法在解决问题时所需的额外空间资源的指标。它衡量的是算法对内存（或存储空间）的使用量。在计算空间复杂度时，一般不考虑输入数据本身所占用的空间，只关注额外所需的空间。因此，空间复杂度主要用来衡量算法对内存的占用情况，帮助我们评估算法的空间效率和优化算法设计。
通常用大O表示法来表示空间复杂度，例如O(1)、O(n)、O(n²)等。
