资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

【蓝桥杯C/C++】代码性能提升技巧：算法选择

创作时间:

作者:

@小白创作中心

【蓝桥杯C/C++】代码性能提升技巧：算法选择

引用

CSDN

https://blog.csdn.net/2201_75539691/article/details/143901641

在蓝桥杯中，算法的选择与优化是决定比赛成败的关键因素之一。无论是代码的时间复杂度还是空间复杂度，合适的算法和优化手段都可以帮助我们大大提升代码性能，降低资源消耗，确保程序能够在严格的时间和内存限制下成功通过所有测试用例。

本文将围绕常用的几种算法策略，详细讨论它们的适用场景、实现方法以及优化技巧，帮助您在竞赛中更灵活地选择最优的解题方案。

贪心算法（Greedy Algorithm）

贪心算法是一种逐步选择局部最优解以期获得全局最优解的策略。它以简单高效的思想解决了一些特定类型的优化问题。虽然贪心策略不能保证对所有问题找到最优解，但对于某些具有"贪心选择性质"的问题，它往往是最简单和最具效率的解决方案。

1.1 贪心算法的基本思路

贪心算法的核心在于通过不断选择局部最优解来逐步构建最终解。每一步做出的选择不可撤销，因此贪心算法适合那些在任何阶段做出局部最优解都能达到全局最优解的问题。

1.2 适用场景

贪心算法适用于那些问题具有以下两个性质：

贪心选择性质：整体的最优解可以通过一系列局部最优解来构造。
最优子结构：子问题的最优解可以成为构造原问题的最优解的一部分。

贪心算法典型的应用场景包括：

区间调度问题：寻找最大数量的不重叠区间。
最短路径问题：Dijkstra 算法用于单源最短路径。
最小生成树问题：Kruskal 算法和 Prim 算法。

1.3 贪心算法的优化技巧

选择合适的数据结构：例如，在求解最小生成树的 Prim 算法中，可以使用最小堆来加速选取最小代价的节点操作，从而使得算法的效率提升到 O((V + E)logV)，其中 V 为节点数，E 为边数。
确保贪心选择的合法性：在应用贪心算法之前，一定要通过严格的数学证明或者充分的测试来确认贪心选择可以保证得到最优解。

1.4 示例：区间调度问题

在区间调度问题中，我们需要选择尽量多的不重叠区间。

思路：首先按照区间的结束时间进行排序，每次选择最早结束且与之前选择不冲突的区间，这样可以保证剩下的时间尽可能多地容纳更多的区间。

#include <vector>
#include <algorithm>
#include <iostream>

struct Interval {
    int start;
    int end;
};

bool compare(Interval a, Interval b) {
    return a.end < b.end;
}

int maxNonOverlappingIntervals(std::vector<Interval>& intervals) {
    std::sort(intervals.begin(), intervals.end(), compare);
    int count = 0;
    int lastEnd = -1;
    for (const auto& interval : intervals) {
        if (interval.start >= lastEnd) {
            count++;
            lastEnd = interval.end;
        }
    }
    return count;
}

int main() {
    std::vector<Interval> intervals = {{1, 3}, {2, 4}, {3, 5}, {5, 7}};
    std::cout << "Maximum number of non-overlapping intervals: " << maxNonOverlappingIntervals(intervals) << std::endl;
    return 0;
}

在这个例子中，贪心选择性质确保了选择尽早结束的区间可以为后续的区间选择提供最大的空间，从而达到全局最优。

分治算法（Divide and Conquer）

分治算法是一种递归解决问题的策略，将原问题分解为规模更小的子问题，然后逐一解决子问题，最终将各个子问题的解组合成原问题的解。分治思想不仅是一种解题方法，还为许多复杂算法（如排序、数值计算等）奠定了基础。

2.1 分治的基本思想

分治法将一个复杂问题分解为两个或更多规模较小的相似子问题，再逐个解决这些子问题。典型的分治算法包括：

快速排序：将数组按照基准元素划分为左右两个子数组，再对两个子数组分别递归排序。
归并排序：将数组分成两个部分，分别排序后再合并。

2.2 适用场景

分治法适用于可以分解为相互独立子问题的问题，例如：

排序问题：快速排序、归并排序。
矩阵乘法：Strassen 算法。
最近点对问题：通过递归分割区域找出最近的两点对。

2.3 分治的优化技巧

减少递归边界的开销：通过设置合理的边界条件来减少递归的次数。可以考虑在数组规模较小时，改为使用插入排序等效率更高的简单算法。
尾递归优化：在可能的情况下，使用尾递归优化，减少递归调用的栈空间消耗。

2.4 示例：归并排序

归并排序是一个经典的分治算法，它通过将数组不断二分，直到每个子数组的长度为1，然后将其合并为有序数组。

#include <vector>
#include <iostream>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + 1 + i];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。其核心在于通过不断分解与合并，确保排序的稳定性与高效性。

动态规划（Dynamic Programming）

动态规划是解决最优子结构问题的利器。与分治不同，动态规划通过记录已经计算过的结果避免重复计算，从而显著提高效率。它适合于那些具有重叠子问题结构的问题。

3.1 动态规划的基本思想

动态规划将问题分解为相互依赖的子问题，并通过自底向上的方式解决这些子问题，同时记录已经求解的结果以供后续使用。动态规划的核心在于通过填表（memoization 或 table）来节省重复计算的开销。

3.2 适用场景

最优路径问题：如求解从矩阵左上角到右下角的最短路径。
背包问题：如 0-1 背包问题、完全背包问题。
序列问题：如最长递增子序列、最长公共子序列。

3.3 动态规划的优化技巧

滚动数组：如果当前状态仅依赖于前一状态，可以采用滚动数组来压缩空间。例如，将二维数组压缩为一维数组，降低空间复杂度。
状态压缩：对于多维状态，可以通过位运算进行状态压缩，减少对内存的占用。

3.4 示例：斐波那契数列

下面是通过动态规划求解斐波那契数列的代码示例：

#include <vector>
#include <iostream>

long long fibonacci(int n) {
    if (n <= 1) return n;
    std::vector<long long> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "Fibonacci of " << n << " is: " << fibonacci(n) << std::endl;
    return 0;
}

斐波那契数列的动态规划解法时间复杂度为 O(n)，而空间复杂度也为 O(n)。如果我们使用滚动数组来存储最近的两个状态，可以进一步将空间复杂度优化到 O(1)。

双指针和滑动窗口（Two Pointers and Sliding Window）

双指针和滑动窗口是一类用于处理数组和字符串中连续区间问题的高效技巧，通常具有 O(n) 的时间复杂度。

4.1 双指针和滑动窗口的基本思想

双指针通过使用两个指针指向序列的不同位置，通常用于解决有序数组中的特定问题，例如求和、寻找满足特定条件的子数组等。滑动窗口通过动态调整窗口的边界来寻找符合条件的子区间。

4.2 适用场景

查找满足特定条件的连续子数组：如求和为指定值的连续子数组。
最长子串问题：如寻找最长无重复字符的子串。

4.3 双指针和滑动窗口的优化技巧

窗口动态调整：通过灵活调整左右指针的位置来控制窗口大小，以最小化时间复杂度。
减少重复计算：通过记录窗口内的状态，避免每次滑动时的重复计算。

4.4 示例：最长不重复子串

#include <string>
#include <unordered_map>
#include <iostream>

int lengthOfLongestSubstring(const std::string& s) {
    std::unordered_map<char, int> charIndex;
    int maxLength = 0, left = 0;
    for (int right = 0; right < s.length(); ++right) {
        char c = s[right];
        if (charIndex.find(c) != charIndex.end() && charIndex[c] >= left) {
            left = charIndex[c] + 1;
        }
        charIndex[c] = right;
        maxLength = std::max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    std::string s = "abcabcbb";
    std::cout << "Length of longest substring without repeating characters: " << lengthOfLongestSubstring(s) << std::endl;
    return 0;
}

在这个例子中，双指针（即滑动窗口）通过维护一个左右指针来动态调整窗口大小，从而在 O(n) 的时间内找到最长的不重复子串。

位运算优化（Bit Manipulation）

位运算是一种高效处理整数的技巧，特别适合用于对数据进行掩码处理和状态压缩的问题。位运算操作符包括与（&）、或（|）、异或（^）、取反（~）等，它们通常比乘法、除法等算术运算符执行得更快。

5.1 适用场景

集合操作：如集合的并、交、补操作。
状态压缩：用于动态规划中的状态压缩，减少空间复杂度。
判断性质：如判断一个数是否为 2 的幂。

5.2 位运算的优化技巧

利用位运算进行加速：例如，乘以 2 等价于左移 1 位，除以 2 等价于右移 1 位。
位掩码：通过位掩码来对某些特定状态进行标记，从而有效地压缩空间和加速计算。

5.3 示例：判断一个数是否为 2 的幂

bool isPowerOfTwo(int n) {
    return (n > 0) && ((n & (n - 1)) == 0);
}

这个例子利用了位运算的特性，n & (n - 1) 可以消除 n 的最低位的 1。因此，如果 n 是 2 的幂，那么它的二进制表示只有一位为 1，n & (n - 1) 的结果必然为 0。

预处理和查表优化

预处理和查表是一种通过预先计算结果以减少运行时复杂度的技巧，特别适合需要频繁查询的问题，例如计算组合数、快速查找质数等。

6.1 适用场景

多次查询：如在一个范围内多次查询组合数、最大公因数等。
筛选问题：如质数筛选。

6.2 预处理和查表的优化技巧

使用数组或哈希表存储预处理结果：例如，在质数筛选中，使用布尔数组记录每个数是否为质数。
线性筛法：用于质数筛选，相对于传统的埃氏筛法，线性筛法在处理大范围时更加高效。

6.3 示例：埃氏筛选法

#include <vector>
#include <iostream>

std::vector<bool> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

int main() {
    int n = 50;
    std::vector<bool> primes = sieveOfEratosthenes(n);
    for (int i = 0; i <= n; ++i) {
        if (primes[i]) {
            std::cout << i << " ";
        }
    }
    return 0;
}

埃氏筛选法的时间复杂度为 O(n log log n)，通过预处理，可以快速判断某个数是否为质数，适用于多次查询。