C++ 阅读时间 13 分钟

改进 C++ 算法复杂度(大 O)的 7 个技巧

分享本文
7 Tips to Improve C++ Algorithm Complexity (Big-O)

理解算法复杂度,特别是大 O 表示法,对于分析和比较算法的效率至关重要。在 C++ 中,和其他编程语言一样,算法的复杂度会显著影响应用的性能和可扩展性。因此,了解如何改进算法复杂度很有用。但首先,让我们来了解最常见的复杂度类别:

1.O(1)——常数时间

示例:通过索引访问数组中的元素。

#include <iostream>

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int index = 2;
    std::cout << "Element at index " << index << " is " << arr[index] << std::endl;  // O(1) operation
    return 0;
}

2.O(log n)——对数时间

示例:在有序数组中进行二分查找。

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

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 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;
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 7;
    int result = binarySearch(arr, target);
    if (result != -1)
        std::cout << "Element found at index " << result << std::endl;
    else
        std::cout << "Element not found" << std::endl;
    return 0;
}

3.O(n)——线性时间

示例:对数组元素求和。

#include <iostream>

int sumArray(const int arr[], int size) {
    int sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += arr[i];
    }
    return sum;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    std::cout << "Sum of array elements is " << sumArray(arr, size) << std::endl;
    return 0;
}

4.O(n log n)——线性对数时间

示例:归并排序算法。

#include <iostream>
#include <vector>

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) {
        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 = {12, 11, 13, 5, 6, 7};
    mergeSort(arr, 0, arr.size() - 1);
    for (int x : arr) std::cout << x << " ";
    std::cout << std::endl;
    return 0;
}

5.O(n^2)——平方时间

示例:冒泡排序算法。

#include <iostream>

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {5, 1, 4, 2, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, size);
    for (int i = 0; i < size; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}

6.O(n^3)——立方时间

示例:检查数组中三个数之和是否等于给定的数。

#include <iostream>

bool findTriplet(int arr[], int n, int sum) {
    for (int i = 0; i < n - 2; ++i) {
        for (int j = i + 1; j < n - 1; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (arr[i] + arr[j] + arr[k] == sum) {
                    std::cout << "Triplet found: " << arr[i] << ", " << arr[j] << ", " << arr[k] << std::endl;
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    int arr[] = {1, 4, 45, 6, 10, 8};
    int sum = 22;
    int size = sizeof(arr) / sizeof(arr[0]);
    if (!findTriplet(arr, size, sum))
        std::cout << "No triplet found" << std::endl;
    return 0;
}

7.O(2^n)——指数时间

示例:递归计算斐波那契数列。

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

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

8.O(n!)——阶乘时间

示例:生成一个字符串的所有排列。

#include <iostream>
#include <string>
#include <algorithm>

void permute(std::string str, int l, int r) {
    if (l == r) {
        std::cout << str << std::endl;
    } else {
        for (int i = l; i <= r; ++i) {
            std::swap(str[l], str[i]);
            permute(str, l + 1, r);
            std::swap(str[l], str[i]); // backtrack
        }
    }
}

int main() {
    std::string str = "ABC";
    permute(str, 0, str.size() - 1);
    return 0;
}

优化大 O 复杂度的技巧

优化算法复杂度通常涉及使用不同的技术来降低算法的时间或空间复杂度。以下是一些优化算法复杂度的常用技术:

1.选择合适的数据结构

选择合适的数据结构对于优化算法的大 O 复杂度至关重要。不同的数据结构为插入、删除、访问和搜索等各种操作提供不同的效率。下面我们将讨论几种常见的数据结构及其典型操作,并给出每种结构的 C++ 示例。

1.1数组

特性:

  • 固定大小
  • 连续内存分配
  • 通过索引快速访问(O(1))
  • 插入和删除较慢(O(n))

使用场景:当元素数量预先已知且需要通过索引快速访问时使用。

C++ 示例:

#include <iostream>

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int index = 2;
    std::cout << "Element at index " << index << " is " << arr[index] << std::endl; // O(1) access
    return 0;
}

1.2.链表

特性:

  • 动态大小
  • 非连续内存分配
  • 快速插入和删除(已知位置时为 O(1))
  • 通过索引访问较慢(O(n))

使用场景:当元素数量未知或可变且需要频繁插入或删除时使用。

C++ 示例:

#include <iostream>

struct Node {
    int data;
    Node* next;
};

void append(Node*& head, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = nullptr;
    if (!head) {
        head = new_node;
        return;
    }
    Node* last = head;
    while (last->next) {
        last = last->next;
    }
    last->next = new_node;
}

void printList(Node* node) {
    while (node) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = nullptr;
    append(head, 1);
    append(head, 2);
    append(head, 3);
    printList(head); // O(n) traversal
    return 0;
}

1.3.哈希表(unordered_map)

特性:

  • 插入、删除和访问的平均时间复杂度为 O(1)
  • 动态大小
  • 非连续内存分配

使用场景:当需要快速访问、插入和删除且元素顺序不重要时使用。

C++ 示例:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> umap;
    umap["one"] = 1;
    umap["two"] = 2;
    umap["three"] = 3;

    std::cout << "Value for key 'two': " << umap["two"] << std::endl; // O(1) access
    return 0;
}

1.4.平衡树(如 std::map、std::set)

特性:

  • 插入、删除和访问的时间复杂度为 O(log n)
  • 元素保持有序

使用场景:当元素必须保持有序且需要相对快速的插入、删除和访问时使用。

C++ 示例:

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> omap;
    omap["one"] = 1;
    omap["two"] = 2;
    omap["three"] = 3;

    std::cout << "Value for key 'two': " << omap["two"] << std::endl; // O(log n) access
    for (const auto& pair : omap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

1.5.堆(优先队列)

特性:

  • 插入和删除的时间复杂度为 O(log n)
  • 访问最大/最小元素的时间复杂度为 O(1)

使用场景:用于动态变化的数据集,当您需要频繁访问最大或最小元素时使用。

C++ 示例:

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "Top element is " << pq.top() << std::endl; // O(1) access to the maximum element

    pq.pop(); // O(log n) deletion
    std::cout << "Top element after pop is " << pq.top() << std::endl;
    return 0;
}

1.6.图

特性:

  • 以邻接表或邻接矩阵表示
  • 邻接表:遍历复杂度为 O(V + E)
  • 邻接矩阵:遍历复杂度为 O(V^2)

使用场景:用于表示实体之间的关系或连接,如社交网络或交通网络。

C++ 示例(邻接表):

#include <iostream>
#include <vector>

void addEdge(std::vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u); // For undirected graph
}

void printGraph(const std::vector<int> adj[], int V) {
    for (int v = 0; v < V; ++v) {
        std::cout << "Adjacency list of vertex " << v << "\n head ";
        for (auto x : adj[v]) std::cout << "-> " << x;
        std::cout << std::endl;
    }
}

int main() {
    int V = 5;
    std::vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 4);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 1, 4);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);

    printGraph(adj, V);
    return 0;
}

2.分治法

将问题分解为更小的子问题,递归地解决每个子问题,然后合并结果,例如:

  • 归并排序:将数组分成两半,分别对每一半排序,然后合并已排序的两半,达到 O(n log n) 的复杂度。
  • 快速排序:基于基准值将数组划分为子数组并对子数组排序,平均复杂度为 O(n log n)。

3.记忆化

  • 一种优化技术,存储开销较大的函数调用结果,并在相同输入再次出现时复用它们。
  • 通常与递归算法结合使用以提高效率。
  • 示例:带记忆化的递归斐波那契将复杂度从 O(2^n) 降至 O(n)。
#include <iostream>
#include <vector>

int fibonacci(int n, std::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];
}

int main() {
    int n = 30;
    std::vector<int> memo(n + 1, -1);
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n, memo) << std::endl;
    return 0;
}

4.预计算与缓存

  • 为可能的输入预先计算结果并存储,以便在执行期间快速查找。
  • 前缀和数组示例:经过 O(n) 的预处理步骤后,可以实现 O(1) 时间的快速区间求和查询。
#include <iostream>
#include <vector>

std::vector<int> computePrefixSum(const std::vector<int>& nums) {
    std::vector<int> prefixSum(nums.size());
    prefixSum[0] = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }
    return prefixSum;
}

int rangeSum(const std::vector<int>& prefixSum, int left, int right) {
    if (left == 0) return prefixSum[right];
    return prefixSum[right] - prefixSum[left - 1];
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::vector<int> prefixSum = computePrefixSum(nums);

    int left = 1, right = 3;
    std::cout << "Sum of range [" << left << ", " << right << "] is " << rangeSum(prefixSum, left, right) << std::endl;
    return 0;
}

5.排序与搜索优化

  • 根据输入的特性选择排序算法(例如,对真实世界数据使用 Timsort)。
  • 对有序数据使用二分查找(O(log n))等高效搜索算法。
#include <iostream>
#include <vector>
#include <algorithm>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 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;
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 7;
    std::cout << "Index of " << target << " is " << binarySearch(arr, target) << std::endl;
    return 0;
}

6.时空权衡

时空权衡涉及在内存使用和执行速度之间取得平衡。在某些情况下,您可以通过使用更多内存来降低算法的时间复杂度,反之亦然。下面是一个使用斐波那契数列演示这一概念的 C++ 示例。

6.1.朴素递归方法(时间未优化,空间低效)

计算斐波那契数列的朴素递归方法具有 O(2^n) 的指数时间复杂度,并且由于反复计算相同的值而占用大量栈空间。

代码:

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 30; // Be careful with large values of n as it will take significant time
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
    return 0;
}

6.2. 带记忆化的动态规划(时间优化,空间优化)

记忆化存储先前计算的结果,以额外内存为代价将时间复杂度降至 O(n)。

代码:

#include <iostream>
#include <vector>

int fibonacci(int n, std::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];
}

int main() {
    int n = 30;
    std::vector<int> memo(n + 1, -1);
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n, memo) << std::endl;
    return 0;
}

6.3. 迭代方法(时间高效,空间高效)

迭代方法以 O(n) 的时间复杂度和 O(1) 的空间复杂度计算斐波那契数列。

代码:

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1, current;
    for (int i = 2; i <= n; ++i) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

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

时空权衡解析

1. 朴素递归方法:

  • 时间复杂度:O(2^n),因为它多次重复计算斐波那契数。
  • 空间复杂度:O(n),因为递归使用了调用栈。

2. 带记忆化的动态规划:

  • 时间复杂度:O(n),因为每个斐波那契数只计算一次。
  • 空间复杂度:O(n),用于在记忆数组中存储先前计算的结果。

3. 迭代方法:

  • 时间复杂度:O(n),用于计算斐波那契数列。
  • 空间复杂度:O(1),因为它只使用少量变量存储中间结果。

7.并行与并发

  • 将工作拆分到多个处理器或线程上,以缩短运行时间。
  • 示例:
  • MapReduce:一种在集群上使用分布式算法处理大型数据集的框架。
  • 并行排序算法:例如并行归并排序。

通过运用这些技术,您通常可以显著提高算法的效率,使您的应用更快、更具可扩展性。

结论

大 O 表示法是理解和分析 C++ 算法效率的基本概念。通过提供算法增长率的高层视图,大 O 表示法使开发者能够预测性能、确保可扩展性并有效地优化代码。在设计和实现算法时,始终要考虑其大 O 复杂度,以便就其是否适合给定问题及其效率做出明智的决策。

#algorithm-analysis#big-o-notation#c++-algorithms#c++-performance#caching#coding-best-practices
分享本文