{"id":1939,"date":"2024-07-01T10:38:07","date_gmt":"2024-07-01T10:38:07","guid":{"rendered":"https:\/\/cppdepend.com\/blog\/?p=1939"},"modified":"2024-07-09T10:46:24","modified_gmt":"2024-07-09T10:46:24","slug":"7-tips-to-improve-the-c-algorithms-complexity-big-o","status":"publish","type":"post","link":"https:\/\/cppdepend.com\/blog\/7-tips-to-improve-the-c-algorithms-complexity-big-o\/","title":{"rendered":"7 Tips to improve the C++ algorithms complexity (Big-O)"},"content":{"rendered":"\n

Understanding algorithm complexity, specifically Big-O notation, is crucial for analyzing and comparing the efficiency of algorithms. In C++, as in other programming languages, the complexity of an algorithm can significantly impact the performance and scalability of an application. So it’s useful to know how to improve the algorithm complexity. But before that let’s explore the most common algorithm complexities:<\/p>\n\n\n\n\n\n\n\n

1. O(1) – Constant Time<\/strong><\/h3>\n\n\n\n

Example:<\/strong> Accessing an element in an array by index.<\/p>\n\n\n\n

#include <iostream>\n\nint main() {\n    int arr[] = {1, 2, 3, 4, 5};\n    int index = 2;\n    std::cout << "Element at index " << index << " is " << arr[index] << std::endl;  \/\/ O(1) operation\n    return 0;\n}<\/pre><\/div>\n\n\n\n
2. O(log n) – Logarithmic Time<\/strong><\/h3>\n\n\n\n
Example:<\/strong> Binary search in a sorted array.<\/p>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <algorithm>\n\nint binarySearch(const std::vector<int>& arr, int target) {\n    int left = 0, right = arr.size() - 1;\n    while (left <= right) {\n        int mid = left + (right - left) \/ 2;\n        if (arr[mid] == target) return mid;\n        if (arr[mid] < target) left = mid + 1;\n        else right = mid - 1;\n    }\n    return -1;\n}\n\nint main() {\n    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};\n    int target = 7;\n    int result = binarySearch(arr, target);\n    if (result != -1)\n        std::cout << "Element found at index " << result << std::endl;\n    else\n        std::cout << "Element not found" << std::endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
3. O(n) – Linear Time<\/strong><\/h3>\n\n\n\n
Example:<\/strong> Summing the elements of an array.<\/p>\n\n\n\n
#include <iostream>\n\nint sumArray(const int arr[], int size) {\n    int sum = 0;\n    for (int i = 0; i < size; ++i) {\n        sum += arr[i];\n    }\n    return sum;\n}\n\nint main() {\n    int arr[] = {1, 2, 3, 4, 5};\n    int size = sizeof(arr) \/ sizeof(arr[0]);\n    std::cout << "Sum of array elements is " << sumArray(arr, size) << std::endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
4. O(n log n) – Linearithmic Time<\/strong><\/h3>\n\n\n\n
Example:<\/strong> Mergesort algorithm.<\/p>\n\n\n\n
#include <iostream>\n#include <vector>\n\nvoid merge(std::vector<int>& arr, int left, int mid, int right) {\n    int n1 = mid - left + 1;\n    int n2 = right - mid;\n    std::vector<int> L(n1), R(n2);\n\n    for (int i = 0; i < n1; ++i)\n        L[i] = arr[left + i];\n    for (int i = 0; i < n2; ++i)\n        R[i] = arr[mid + 1 + i];\n\n    int i = 0, j = 0, k = left;\n    while (i < n1 && j < n2) {\n        if (L[i] <= R[j]) {\n            arr[k++] = L[i++];\n        } else {\n            arr[k++] = R[j++];\n        }\n    }\n    while (i < n1) arr[k++] = L[i++];\n    while (j < n2) arr[k++] = R[j++];\n}\n\nvoid mergeSort(std::vector<int>& arr, int left, int right) {\n    if (left < right) {\n        int mid = left + (right - left) \/ 2;\n        mergeSort(arr, left, mid);\n        mergeSort(arr, mid + 1, right);\n        merge(arr, left, mid, right);\n    }\n}\n\nint main() {\n    std::vector<int> arr = {12, 11, 13, 5, 6, 7};\n    mergeSort(arr, 0, arr.size() - 1);\n    for (int x : arr) std::cout << x << " ";\n    std::cout << std::endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
5. O(n^2) – Quadratic Time<\/strong><\/h3>\n\n\n\n
Example:<\/strong> Bubble sort algorithm.<\/p>\n\n\n\n
#include <iostream>\n\nvoid bubbleSort(int arr[], int size) {\n    for (int i = 0; i < size - 1; ++i) {\n        for (int j = 0; j < size - i - 1; ++j) {\n            if (arr[j] > arr[j + 1]) {\n                std::swap(arr[j], arr[j + 1]);\n            }\n        }\n    }\n}\n\nint main() {\n    int arr[] = {5, 1, 4, 2, 8};\n    int size = sizeof(arr) \/ sizeof(arr[0]);\n    bubbleSort(arr, size);\n    for (int i = 0; i < size; ++i)\n        std::cout << arr[i] << " ";\n    std::cout << std::endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
6. O(n^3) – Cubic Time<\/strong><\/h3>\n\n\n\n
Example:<\/strong> Checking if three numbers in an array sum up to a given number.<\/p>\n\n\n\n
#include <iostream>\n\nbool findTriplet(int arr[], int n, int sum) {\n    for (int i = 0; i < n - 2; ++i) {\n        for (int j = i + 1; j < n - 1; ++j) {\n            for (int k = j + 1; k < n; ++k) {\n                if (arr[i] + arr[j] + arr[k] == sum) {\n                    std::cout << "Triplet found: " << arr[i] << ", " << arr[j] << ", " << arr[k] << std::endl;\n                    return true;\n                }\n            }\n        }\n    }\n    return false;\n}\n\nint main() {\n    int arr[] = {1, 4, 45, 6, 10, 8};\n    int sum = 22;\n    int size = sizeof(arr) \/ sizeof(arr[0]);\n    if (!findTriplet(arr, size, sum))\n        std::cout << "No triplet found" << std::endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
7. O(2^n) – Exponential Time<\/strong><\/h3>\n\n\n\n
Example:<\/strong> Recursive calculation of Fibonacci numbers.<\/p>\n\n\n\n
#include <iostream>\n\nint fibonacci(int n) {\n    if (n <= 1) return n;\n    return fibonacci(n - 1) + fibonacci(n - 2);\n}\n\nint main() {\n    int n = 5;\n    std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
8. O(n!) – Factorial Time<\/strong><\/h3>\n\n\n\n
Example:<\/strong> Generating all permutations of a string.<\/p>\n\n\n\n
#include <iostream>\n#include <string>\n#include <algorithm>\n\nvoid permute(std::string str, int l, int r) {\n    if (l == r) {\n        std::cout << str << std::endl;\n    } else {\n        for (int i = l; i <= r; ++i) {\n            std::swap(str[l], str[i]);\n            permute(str, l + 1, r);\n            std::swap(str[l], str[i]); \/\/ backtrack\n        }\n    }\n}\n\nint main() {\n    std::string str = "ABC";\n    permute(str, 0, str.size() - 1);\n    return 0;\n}<\/pre><\/div>\n\n\n\n
Tips to optimize the Big-O<\/h3>\n\n\n\n
Optimizing the algorithm complexity often involves using different techniques to reduce the time or space complexity of an algorithm. Here are some common techniques to optimize algorithm complexity:<\/p>\n\n\n\n
1. Choosing the Right Data Structures<\/strong><\/h3>\n\n\n\n
Choosing the right data structures is crucial for optimizing the Big O complexity of your algorithms. Different data structures provide different efficiencies for various operations such as insertion, deletion, access, and search. Below, I’ll discuss several common data structures, their typical operations, and provide C++ examples for each.<\/p>\n\n\n\n
1. 1 Arrays<\/strong><\/h3>\n\n\n\n
Properties:<\/strong><\/p>\n\n\n\n
    \n
  • Fixed size<\/li>\n\n\n\n
  • Contiguous memory allocation<\/li>\n\n\n\n
  • Fast access by index (O(1))<\/li>\n\n\n\n
  • Slow insertions and deletions (O(n))<\/li>\n<\/ul>\n\n\n\n
    Use Cases:<\/strong> When the number of elements is known in advance and fast access by index is required.<\/p>\n\n\n\n
    C++ Example:<\/strong><\/p>\n\n\n\n
    #include <iostream>\n\nint main() {\n    int arr[] = {1, 2, 3, 4, 5};\n    int index = 2;\n    std::cout << "Element at index " << index << " is " << arr[index] << std::endl; \/\/ O(1) access\n    return 0;\n}<\/pre><\/div>\n\n\n\n
    1.2. Linked Lists<\/strong><\/h3>\n\n\n\n
    Properties:<\/strong><\/p>\n\n\n\n
      \n
    • Dynamic size<\/li>\n\n\n\n
    • Non-contiguous memory allocation<\/li>\n\n\n\n
    • Fast insertions and deletions (O(1) if the position is known)<\/li>\n\n\n\n
    • Slow access by index (O(n))<\/li>\n<\/ul>\n\n\n\n
      Use Cases:<\/strong> When the number of elements is unknown or variable, and frequent insertions\/deletions are required.<\/p>\n\n\n\n
      C++ Example:<\/strong><\/p>\n\n\n\n
      #include <iostream>\n\nstruct Node {\n    int data;\n    Node* next;\n};\n\nvoid append(Node*& head, int new_data) {\n    Node* new_node = new Node();\n    new_node->data = new_data;\n    new_node->next = nullptr;\n    if (!head) {\n        head = new_node;\n        return;\n    }\n    Node* last = head;\n    while (last->next) {\n        last = last->next;\n    }\n    last->next = new_node;\n}\n\nvoid printList(Node* node) {\n    while (node) {\n        std::cout << node->data << " ";\n        node = node->next;\n    }\n    std::cout << std::endl;\n}\n\nint main() {\n    Node* head = nullptr;\n    append(head, 1);\n    append(head, 2);\n    append(head, 3);\n    printList(head); \/\/ O(n) traversal\n    return 0;\n}<\/pre><\/div>\n\n\n\n
      1.3. Hash Tables (unordered_map)<\/strong><\/h3>\n\n\n\n
      Properties:<\/strong><\/p>\n\n\n\n
        \n
      • Average O(1) time complexity for insertions, deletions, and access<\/li>\n\n\n\n
      • Dynamic size<\/li>\n\n\n\n
      • Non-contiguous memory allocation<\/li>\n<\/ul>\n\n\n\n
        Use Cases:<\/strong> When fast access, insertion, and deletion are required, and the order of elements is not important.<\/p>\n\n\n\n
        C++ Example:<\/strong><\/p>\n\n\n\n
        #include <iostream>\n#include <unordered_map>\n\nint main() {\n    std::unordered_map<std::string, int> umap;\n    umap["one"] = 1;\n    umap["two"] = 2;\n    umap["three"] = 3;\n\n    std::cout << "Value for key 'two': " << umap["two"] << std::endl; \/\/ O(1) access\n    return 0;\n}<\/pre><\/div>\n\n\n\n
        1.4. Balanced Trees (e.g., std::map, std::set)<\/strong><\/h3>\n\n\n\n
        Properties:<\/strong><\/p>\n\n\n\n
          \n
        • O(log n) time complexity for insertions, deletions, and access<\/li>\n\n\n\n
        • Elements are kept in sorted order<\/li>\n<\/ul>\n\n\n\n
          Use Cases:<\/strong> When sorted order of elements is required and relatively fast insertions, deletions, and access are needed.<\/p>\n\n\n\n
          C++ Example:<\/strong><\/p>\n\n\n\n
          #include <iostream>\n#include <map>\n\nint main() {\n    std::map<std::string, int> omap;\n    omap["one"] = 1;\n    omap["two"] = 2;\n    omap["three"] = 3;\n\n    std::cout << "Value for key 'two': " << omap["two"] << std::endl; \/\/ O(log n) access\n    for (const auto& pair : omap) {\n        std::cout << pair.first << ": " << pair.second << std::endl;\n    }\n    return 0;\n}<\/pre><\/div>\n\n\n\n
          1.5. Heaps (Priority Queue)<\/strong><\/h3>\n\n\n\n
          Properties:<\/strong><\/p>\n\n\n\n
            \n
          • O(log n) time complexity for insertions and deletions<\/li>\n\n\n\n
          • O(1) time complexity for access to the maximum\/minimum element<\/li>\n<\/ul>\n\n\n\n
            Use Cases:<\/strong> When a dynamically changing dataset is needed and you frequently need to access the largest or smallest element.<\/p>\n\n\n\n
            C++ Example:<\/strong><\/p>\n\n\n\n
            #include <iostream>\n#include <queue>\n#include <vector>\n\nint main() {\n    std::priority_queue<int> pq;\n    pq.push(10);\n    pq.push(30);\n    pq.push(20);\n\n    std::cout << "Top element is " << pq.top() << std::endl; \/\/ O(1) access to the maximum element\n\n    pq.pop(); \/\/ O(log n) deletion\n    std::cout << "Top element after pop is " << pq.top() << std::endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
            1.6. Graphs<\/strong><\/h3>\n\n\n\n
            Properties:<\/strong><\/p>\n\n\n\n
              \n
            • Represented as adjacency lists or adjacency matrices<\/li>\n\n\n\n
            • Adjacency list: O(V + E) for traversal<\/li>\n\n\n\n
            • Adjacency matrix: O(V^2) for traversal<\/li>\n<\/ul>\n\n\n\n
              Use Cases:<\/strong> When representing relationships or connections between entities, such as social networks or transportation networks.<\/p>\n\n\n\n
              C++ Example (Adjacency List):<\/strong><\/p>\n\n\n\n
              #include <iostream>\n#include <vector>\n\nvoid addEdge(std::vector<int> adj[], int u, int v) {\n    adj[u].push_back(v);\n    adj[v].push_back(u); \/\/ For undirected graph\n}\n\nvoid printGraph(const std::vector<int> adj[], int V) {\n    for (int v = 0; v < V; ++v) {\n        std::cout << "Adjacency list of vertex " << v << "\\n head ";\n        for (auto x : adj[v]) std::cout << "-> " << x;\n        std::cout << std::endl;\n    }\n}\n\nint main() {\n    int V = 5;\n    std::vector<int> adj[V];\n    addEdge(adj, 0, 1);\n    addEdge(adj, 0, 4);\n    addEdge(adj, 1, 2);\n    addEdge(adj, 1, 3);\n    addEdge(adj, 1, 4);\n    addEdge(adj, 2, 3);\n    addEdge(adj, 3, 4);\n\n    printGraph(adj, V);\n    return 0;\n}<\/pre><\/div>\n\n\n\n
              2. Divide and Conquer<\/strong><\/h3>\n\n\n\n
              Breaks the problem into smaller subproblems, solves each subproblem recursively, and then combines the solutions, like:<\/p>\n\n\n\n