跳至主要內容
算法复杂度

1. 什么是算法复杂度

算法复杂度是衡量一个算法在执行过程中的资源消耗量的指标。通常分为 时间复杂度 和 空间复杂度 两种：

  • 时间复杂度：表示算法执行所需的时间。
  • 空间复杂度：表示算法执行过程中所需的存储空间。

2. 大O表示法

大O表示法用于描述算法复杂度的上界，主要关注的是算法在输入规模很大时，性能的增长情况。

  • O(1)：常数时间复杂度，无论输入大小如何，算法总是执行相同数量的步骤。
  • O(log n)：对数时间复杂度，随着输入规模的增加，算法执行的步骤按对数关系增加。
  • O(n)：线性时间复杂度，算法执行的步骤与输入规模成正比。
  • O(n log n)：线性对数时间复杂度，比线性时间复杂度稍差一些，常见于一些高级排序算法。
  • O(n^2)：平方时间复杂度，步骤数量随着输入规模的平方增加，常见于一些简单的嵌套循环。
  • O(2^n)：指数时间复杂度，步骤数量随着输入规模的指数增长。
  • O(n!)：阶乘时间复杂度，极其低效的算法。
Lxy2024/9/15大约 10 分钟算法C++算法
动态规划

动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

在本节中，我们从一个经典例题入手，先给出它的暴力回溯解法，观察其中包含的重叠子问题，再逐步导出更高效的动态规划解法。

"爬楼梯"

给定一个共有 nn 阶的楼梯，你每步可以上 11 阶或者 22 阶，请问有多少种方案可以爬到楼顶？

Lxy2024/9/15大约 48 分钟算法C++算法
分治算法

基本概念

分治算法是一种通过将较大规模的问题分解为较小规模的问题，并对这些较小问题求解，从而解决整个问题的算法。分治算法的核心思想是递归地将问题拆分并解决，这种方法在二分法中尤为明显。

分治算法（Divide and Conquer）是一种重要的算法设计范式。它通过将一个复杂的问题分解成若干个规模较小且相似的子问题，递归地解决这些子问题，再将子问题的解组合起来得到原问题的解。

分治算法的基本步骤

  1. 分解（Divide）：

    • 将原问题分解成若干个规模较小的子问题。这些子问题通常是原问题的简化版本。

  2. 解决（Conquer）：

    • 如果子问题规模足够小，直接解决；否则，递归地解决每个子问题。

  3. 合并（Combine）：

    • 将子问题的解合并成原问题的解。
Lxy2024/9/1大约 9 分钟算法C++算法
贪心算法

基本概念

贪心算法（Greedy Algorithm）在解决问题时，总是做出在当前看来是最优的选择。它只考虑局部最优解，并不从整体最优的角度考虑。因此，贪心算法的关键在于选择合适的贪心策略，该策略必须具备无后效性，即某个状态以后的过程不会影响之前的状态，只与当前状态相关。

注意：贪心算法并不适用于所有问题，选择的策略必须仔细分析是否满足无后效性，否则可能无法得到整体最优解。

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望能够得到问题的全局最优解的算法。贪心算法的核心思想是局部最优策略的累积能够带来全局最优。

Lxy2024/9/1大约 10 分钟算法C++算法
搜索与回溯算法

搜索与回溯是计算机解题中常用的算法技术，特别适用于那些没有固定计算法则的问题。回溯是一种搜索算法中的控制策略，其核心思想是：尝试通过不断选择和探索不同的路径解决问题，如果当前路径行不通，就回退一步重新选择，直到找到解决方案或证明无解为止。
比如在迷宫问题中，探险者需要找到从入口到出口的路径。初始时，可以随意选择一个方向前进，一步步尝试前进。如果碰到死胡同，说明当前路径行不通，需要回退一步重新选择方向。这种不断前进、回退的过程，正是回溯算法的体现。

回溯算法的基本框架

回溯算法通常通过递归实现。下面提供两个常见的回溯算法框架

框架一：先遍历

Lxy2024/6/10大约 8 分钟算法C++算法
递推算法

递推算法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是在计算机数值计算中一个重要的算法。这种算法的特点是：一个问题的求解需要经过一系列的计算，在已知条件和所求问题之间存在某种相互联系的关系。在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，这种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般来说，可以将递推算法看成是一种特殊的迭代算法。

Lxy2024/6/1大约 27 分钟算法C++算法
排序算法

排序算法

在 C++ 中，排序算法是用来对数据进行排序的一种重要算法。排序算法根据其实现原理和时间复杂度的不同，可以分为多种不同类型。以下是一些常见的排序算法及其概念：

常见排序概览

  1. 冒泡排序（Bubble Sort）：
    冒泡排序是一种简单的排序算法，它重复地走访要排序的元素序列，依次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。直到没有任何一对元素需要交换为止。

  2. 选择排序（Selection Sort）：
    选择排序每次从待排序的数据元素中选出最小（或最大）的元素，放在已排序的序列末尾，直到全部元素排序完成。

  3. 插入排序（Insertion Sort）：
    插入排序每次从未排序的部分中取出一个元素，将其插入到已排序部分的适当位置，使得已排序部分仍然有序。

  4. 快速排序（Quick Sort）：
    快速排序是一种分治法的排序算法，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小，然后再分别对这两部分继续进行快速排序，直到整个序列有序。

  5. 归并排序（Merge Sort）：
    归并排序是一种分治法的排序算法，它将待排序的序列递归地分成两个子序列，然后对这两个子序列分别进行归并排序，最后将排好序的子序列合并成一个有序的序列。

  6. 堆排序（Heap Sort）：
    堆排序利用了堆这种数据结构的性质，将待排序的数据构建成一个最大堆或最小堆，然后利用堆的性质将堆顶元素与堆的最后一个元素交换，并重新调整堆，重复这个过程直到堆中的所有元素都有序。

  7. 计数排序（Counting Sort）：
    计数排序是一种非基于比较的排序算法，它的核心思想是统计待排序序列中每个元素的个数，然后根据统计信息将元素放回到正确的位置上。

  8. 桶排序（Bucket Sort）：
    桶排序将待排序的数据分到有限数量的桶中，然后分别对每个桶中的数据进行排序，最后按照桶的顺序依次将各个桶中的数据合并起来。

Lxy2024/4/26大约 52 分钟算法C++算法
高精度计算

高精度计算

利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。

高精度计算中需要处理好以下几个问题：

1. 数据的接收方法和存储方法

数据的接收和存储：当输入的数很长时，可采用字符串方式输入，这样可输入位数很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。

void init(int a[]) {
    // 传入一个数组
    string s;
    cin >> s; // 读入字符串s
    a[0] = s.length(); // 用a[0]计算字符申s的位数
    for(int i = 1; i <= a[0]; i++) {
        a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
    }
}
Lxy2024/3/30大约 28 分钟算法C++算法