L8_08 算法优化

一、不同算法求解问题的差异分析

1.1 问题求解的不同策略

cpp

// 同一个问题可以用不同算法解决
// 例：排序问题

// 策略1：交换相邻元素
void bubbleSort(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr.size() - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}
// O(n²)

// 策略2：分治
void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left + (right - left) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++; j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}
// O(n log n)

// 策略3：利用额外空间
void countingSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    vector<int> count(max_val + 1, 0);
    
    for (int num : arr) count[num]++;
    
    int idx = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i]--) {
            arr[idx++] = i;
        }
    }
}
// O(n + k)

1.2 算法选择依据

cpp

// 选择算法时需要考虑：
// 1. 时间复杂度
// 2. 空间复杂度
// 3. 数据规模
// 4. 数据特性（是否有序、是否整数等）
// 5. 稳定性要求
// 6. 实现复杂度

二、算法优化的一般方法

2.1 时间复杂度优化

cpp

// 优化方法1：减少重复计算
// 未优化
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2); // 大量重复计算
}

// 优化后（记忆化）
int fibonacci(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
    return memo[n];
}

2.2 空间复杂度优化

cpp

// 优化方法2：滚动数组
// 未优化
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

// 优化后
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j-1];
        }
    }
    return dp[n-1];
}

2.3 剪枝优化

cpp

// 优化方法3：提前终止
void backtrack(vector<int>& candidates, int target, int start, 
              vector<int>& path, vector<vector<int>>& result) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    
    for (int i = start; i < candidates.size(); i++) {
        // 剪枝：如果当前元素已经大于剩余目标，后续元素也一定大于
        if (candidates[i] > target) break;
        
        // 剪枝：跳过重复元素
        if (i > start && candidates[i] == candidates[i-1]) continue;
        
        path.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], i + 1, path, result);
        path.pop_back();
    }
}

2.4 算法替换

cpp

// 优化方法4：选择更高效的算法
// 问题：求第k大的元素

// 方法1：排序后取第k个
int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
}
// O(n log n)

// 方法2：快速选择
int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];
    
    int pivot = nums[left + (right - left) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (nums[i] > pivot) i++;
        while (nums[j] < pivot) j--;
        if (i <= j) swap(nums[i++], nums[j--]);
    }
    
    int leftSize = i - left;
    if (k <= leftSize) return quickSelect(nums, left, i-1, k);
    return quickSelect(nums, i, right, k - leftSize);
}
// 平均 O(n)，最坏 O(n²)

三、根据数学知识优化算法

3.1 利用数学公式

cpp

// 问题：求 1 + 2 + ... + n

// 方法1：循环累加
int sum(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}
// O(n)

// 方法2：利用等差数列求和公式
int sum(int n) {
    return n * (n + 1) / 2;
}
// O(1)

3.2 利用数论性质

cpp

// 问题：求最大公约数

// 方法1：暴力枚举
int gcd(int a, int b) {
    int min_val = min(a, b);
    for (int i = min_val; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1;
}
// O(min(a,b))

// 方法2：欧几里得算法
int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
// O(log min(a,b))

3.3 利用组合数学

cpp

// 问题：求组合数 C(n, k)

// 方法1：直接计算（可能溢出）
long long combination(int n, int k) {
    long long numerator = 1;
    for (int i = n; i > n - k; i--) {
        numerator *= i;
    }
    long long denominator = 1;
    for (int i = 1; i <= k; i++) {
        denominator *= i;
    }
    return numerator / denominator;
}

// 方法2：递推计算（避免溢出）
long long combination(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    k = min(k, n - k);
    long long result = 1;
    for (int i = 0; i < k; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

3.4 利用概率期望

cpp

// 问题：蓄水池抽样
// 从数据流中随机选取k个元素

class ReservoirSampling {
private:
    vector<int> reservoir;
    int k;
    int count;
    
public:
    ReservoirSampling(int k) : k(k), count(0) {
        reservoir.resize(k);
    }
    
    void add(int num) {
        count++;
        if (count <= k) {
            reservoir[count - 1] = num;
        } else {
            // 以 k/count 的概率替换
            int rand_idx = rand() % count;
            if (rand_idx < k) {
                reservoir[rand_idx] = num;
            }
        }
    }
    
    vector<int> getSample() {
        return reservoir;
    }
};

四、算法优化实例

4.1 字符串匹配优化

cpp

// 朴素算法
int naiveSearch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i+j] == pattern[j]) {
            j++;
        }
        if (j == m) return i;
    }
    return -1;
}
// O(n*m)

// KMP算法
vector<int> computePrefix(string pattern) {
    int m = pattern.size();
    vector<int> prefix(m, 0);
    int len = 0;
    
    for (int i = 1; i < m; ) {
        if (pattern[i] == pattern[len]) {
            prefix[i++] = ++len;
        } else {
            if (len != 0) len = prefix[len-1];
            else prefix[i++] = 0;
        }
    }
    return prefix;
}

int kmpSearch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> prefix = computePrefix(pattern);
    
    int i = 0, j = 0;
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++; j++;
        }
        if (j == m) return i - j;
        else if (i < n && pattern[j] != text[i]) {
            if (j != 0) j = prefix[j-1];
            else i++;
        }
    }
    return -1;
}
// O(n + m)

4.2 动态规划优化

cpp

// 问题：最长上升子序列

// O(n²) 解法
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

// O(n log n) 解法
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

4.3 图算法优化

cpp

// 问题：单源最短路径

// Dijkstra（优先队列优化）
vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
// O((V+E)logV)

五、算法优化策略总结

5.1 优化策略分类

策略类型	具体方法	适用场景
减少计算	记忆化、动态规划	重复子问题
减少空间	滚动数组、原地算法	空间受限
提前终止	剪枝、分支限界	搜索问题
算法替换	选择更优算法	复杂度较高
数学优化	公式推导、数论	数学问题
数据结构	使用合适的数据结构	查询频繁

5.2 优化原则

cpp

// 1. 先正确性，后优化
// 2. 避免过早优化
// 3. 测量瓶颈后再优化
// 4. 保持代码可读性
// 5. 考虑常数因子

5.3 性能测试方法

cpp

#include <chrono>

template<typename Func>
long long measureTime(Func func, int iterations = 1) {
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < iterations; i++) {
        func();
    }
    auto end = chrono::high_resolution_clock::now();
    return chrono::duration_cast<chrono::microseconds>(end - start).count() / iterations;
}

// 使用示例
// auto time = measureTime([&]() { quickSort(arr, 0, arr.size()-1); });

六、算法优化的权衡

6.1 时间空间权衡

cpp

// 有时需要在时间和空间之间做出选择

// 例：斐波那契数列
// 时间优先：矩阵快速幂 O(log n)
// 空间优先：迭代 O(1) 空间

// 例：缓存策略
// 时间优先：缓存所有结果
// 空间优先：按需计算

6.2 复杂度与常数因子

cpp

// 理论复杂度 vs 实际性能

// O(n log n) 的算法可能在小规模数据上不如 O(n²)
// 因为常数因子较大

// 例：快速排序 vs 插入排序
// 小规模数据：插入排序更快
// 大规模数据：快速排序更快

// 解决方案：混合排序
void hybridSort(vector<int>& arr, int threshold = 10) {
    if (arr.size() <= threshold) {
        insertionSort(arr);
    } else {
        quickSort(arr, 0, arr.size() - 1);
    }
}

6.3 并行与分布式优化

cpp

// 利用多线程或分布式计算

// 例：归并排序的并行实现
void parallelMergeSort(vector<int>& arr, int numThreads) {
    if (arr.size() <= 1) return;
    
    if (numThreads > 1) {
        int mid = arr.size() / 2;
        vector<int> left(arr.begin(), arr.begin() + mid);
        vector<int> right(arr.begin() + mid, arr.end());
        
        // 并行处理
        thread leftThread(parallelMergeSort, ref(left), numThreads / 2);
        thread rightThread(parallelMergeSort, ref(right), numThreads / 2);
        
        leftThread.join();
        rightThread.join();
        
        merge(left, right, arr);
    } else {
        mergeSort(arr);
    }
}

七、总结

cpp

// 算法优化的核心原则：
// 1. 分析瓶颈：找出最耗时的部分
// 2. 选择合适的数据结构
// 3. 利用数学性质
// 4. 考虑时间空间权衡
// 5. 测试验证优化效果

// 优化步骤：
// 1. 分析问题特性
// 2. 选择合适算法
// 3. 实现并测试
// 4. 分析性能瓶颈
// 5. 应用优化策略
// 6. 验证优化效果

L8_08 算法优化 ​

一、不同算法求解问题的差异分析 ​

1.1 问题求解的不同策略 ​

1.2 算法选择依据 ​

二、算法优化的一般方法 ​

2.1 时间复杂度优化 ​

2.2 空间复杂度优化 ​

2.3 剪枝优化 ​

2.4 算法替换 ​

三、根据数学知识优化算法 ​

3.1 利用数学公式 ​

3.2 利用数论性质 ​

3.3 利用组合数学 ​

3.4 利用概率期望 ​

四、算法优化实例 ​

4.1 字符串匹配优化 ​

4.2 动态规划优化 ​

4.3 图算法优化 ​

五、算法优化策略总结 ​

5.1 优化策略分类 ​

5.2 优化原则 ​

5.3 性能测试方法 ​

六、算法优化的权衡 ​

6.1 时间空间权衡 ​

6.2 复杂度与常数因子 ​

6.3 并行与分布式优化 ​

七、总结 ​

L8_08 算法优化

一、不同算法求解问题的差异分析

1.1 问题求解的不同策略

1.2 算法选择依据

二、算法优化的一般方法

2.1 时间复杂度优化

2.2 空间复杂度优化

2.3 剪枝优化

2.4 算法替换

三、根据数学知识优化算法

3.1 利用数学公式

3.2 利用数论性质

3.3 利用组合数学

3.4 利用概率期望

四、算法优化实例

4.1 字符串匹配优化

4.2 动态规划优化

4.3 图算法优化

五、算法优化策略总结

5.1 优化策略分类

5.2 优化原则

5.3 性能测试方法

六、算法优化的权衡

6.1 时间空间权衡

6.2 复杂度与常数因子

6.3 并行与分布式优化

七、总结