Khóa học C++

Appearance

📊 Độ phức tạp thuật toán và Big-O ​

📖 Giới thiệu ​

Phân tích độ phức tạp thuật toán là kỹ năng cốt lõi trong lập trình, giúp đánh giá hiệu suất của code và lựa chọn giải pháp tối ưu. Big-O notation là ngôn ngữ toán học để mô tả cách thời gian thực thi và không gian bộ nhớ tăng theo kích thước đầu vào.

Tại sao cần phân tích độ phức tạp?

  • Performance Prediction: Dự đoán hiệu suất với dữ liệu lớn
  • Algorithm Comparison: So sánh các thuật toán khác nhau
  • Scalability: Hiểu cách code scale với data size
  • Optimization: Identify bottlenecks và optimize code

Hai loại độ phức tạp chính:

  • Time Complexity: Thời gian thực thi theo kích thước input
  • Space Complexity: Bộ nhớ sử dụng theo kích thước input

Real-world Impact:

  • Database queries: Index design cho O(log n) lookup
  • Social networks: Friend recommendation algorithms
  • Search engines: Page ranking và indexing
  • Gaming: Real-time collision detection
  • Machine Learning: Training algorithms trên big data

🔧 Cú pháp ​

Big-O Notation Basics ​

cpp
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
using namespace std;

// O(1) - Constant Time
int getFirstElement(const vector<int>& arr) {
    if (arr.empty()) return -1;
    return arr[0];  // Always takes same time regardless of array size
}

// O(n) - Linear Time
int findElement(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {  // Loop through all elements
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;  // Worst case: check all n elements
}

// O(log n) - Logarithmic Time
int binarySearch(const vector<int>& sortedArr, int target) {
    int left = 0, right = sortedArr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (sortedArr[mid] == target) {
            return mid;
        } else if (sortedArr[mid] < target) {
            left = mid + 1;  // Eliminate half of remaining elements
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// O(n²) - Quadratic Time
vector<pair<int, int>> findAllPairs(const vector<int>& arr) {
    vector<pair<int, int>> pairs;
    
    for (int i = 0; i < arr.size(); i++) {      // Outer loop: n iterations
        for (int j = i + 1; j < arr.size(); j++) { // Inner loop: up to n iterations
            pairs.push_back({arr[i], arr[j]});     // Total: n × n = n² operations
        }
    }
    return pairs;
}

// O(n log n) - Linearithmic Time
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);      // Divide: log n levels
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);   // Conquer: n operations per level
    }
    // Total: n × log n
}

Space Complexity Examples ​

cpp
// O(1) Space - Constant Space
void swapElements(vector<int>& arr, int i, int j) {
    int temp = arr[i];  // Only uses constant extra space
    arr[i] = arr[j];
    arr[j] = temp;
}

// O(n) Space - Linear Space
vector<int> createCopy(const vector<int>& original) {
    vector<int> copy = original;  // Creates copy of size n
    return copy;
}

// O(log n) Space - Logarithmic Space (due to recursion stack)
int recursiveBinarySearch(const vector<int>& arr, int target, int left, int right) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return recursiveBinarySearch(arr, target, mid + 1, right);  // Stack depth: log n
    } else {
        return recursiveBinarySearch(arr, target, left, mid - 1);
    }
}

// O(n²) Space - Quadratic Space
vector<vector<int>> createMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n, 0));  // n × n = n² space
    return matrix;
}

Complexity Analysis Patterns ​

cpp
// Pattern 1: Single Loop = O(n)
void printArray(const vector<int>& arr) {
    for (int x : arr) {      // n iterations
        cout << x << " ";    // O(1) operation
    }
    // Total: O(n)
}

// Pattern 2: Nested Loops = O(n²), O(n³), etc.
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {           // n iterations
        for (int j = 0; j < n - i - 1; j++) { // up to n iterations
            if (arr[j] > arr[j + 1]) {        // O(1) operation
                swap(arr[j], arr[j + 1]);
            }
        }
    }
    // Total: O(n²)
}

// Pattern 3: Divide and Conquer = O(log n) or O(n log n)
int power(int base, int exp) {
    if (exp == 0) return 1;
    
    int half = power(base, exp / 2);  // Divide by 2 each time = log n levels
    
    if (exp % 2 == 0) {
        return half * half;
    } else {
        return half * half * base;
    }
    // Total: O(log n)
}

// Pattern 4: Tree Traversal = O(n) where n is number of nodes
void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);   // Visit left subtree
        cout << root->val << " ";       // Process current node
        inorderTraversal(root->right);  // Visit right subtree
    }
    // Each node visited exactly once: O(n)
}

🔬 Phân tích & Giải thích chi tiết ​

Big-O Hierarchy (từ tốt nhất đến tệ nhất) ​

1. O(1) - Constant Time

  • Thời gian thực thi không đổi
  • Examples: Array access, hash table lookup (average case)
  • Best case scenario

2. O(log n) - Logarithmic Time

  • Giảm một nửa problem size mỗi step
  • Examples: Binary search, balanced tree operations
  • Very efficient for large datasets

3. O(n) - Linear Time

  • Thời gian tỷ lệ thuận với input size
  • Examples: Linear search, single pass through array
  • Generally acceptable

4. O(n log n) - Linearithmic Time

  • Combine linear và logarithmic
  • Examples: Efficient sorting (merge sort, heap sort)
  • Best we can do for comparison-based sorting

5. O(n²) - Quadratic Time

  • Nested loops over input
  • Examples: Bubble sort, simple nested iterations
  • Becomes slow with large datasets

6. O(2ⁿ) - Exponential Time

  • Time doubles with each additional input
  • Examples: Recursive Fibonacci (naive), brute force combinations
  • Impractical for large inputs

Best, Average, và Worst Case ​

cpp
// Example: Finding element in array
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

// Best Case: O(1) - Element is at first position
int findBestCase = findElement(arr, 1);     // Found immediately

// Average Case: O(n/2) = O(n) - Element is in middle
int findAverage = findElement(arr, 9);      // Check half the elements

// Worst Case: O(n) - Element is at last position or not found
int findWorst = findElement(arr, 15);       // Check all elements
int findNotFound = findElement(arr, 20);    // Check all elements, not found

Amortized Analysis ​

cpp
// Dynamic Array (like std::vector)
class DynamicArray {
private:
    int* data;
    size_t size;
    size_t capacity;
    
public:
    void push_back(int value) {
        if (size >= capacity) {
            // Resize: O(n) operation occasionally
            capacity = (capacity == 0) ? 1 : capacity * 2;
            int* newData = new int[capacity];
            for (size_t i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            delete[] data;
            data = newData;
        }
        
        data[size++] = value;  // O(1) operation most of the time
    }
    
    // Amortized O(1): 
    // - Most insertions are O(1)
    // - Occasional O(n) resize
    // - Average over many operations: O(1)
};

Space-Time Tradeoffs ​

cpp
// Time-optimized: O(1) lookup, O(n) space
class FastLookup {
private:
    unordered_map<int, string> cache;  // Extra space for speed
    
public:
    string getValue(int key) {
        return cache[key];  // O(1) average case
    }
};

// Space-optimized: O(n) lookup, O(1) space
class SpaceEfficient {
private:
    vector<pair<int, string>> data;  // Minimal space usage
    
public:
    string getValue(int key) {
        for (const auto& pair : data) {  // O(n) lookup
            if (pair.first == key) {
                return pair.second;
            }
        }
        return "";
    }
};

💻 Ví dụ minh họa ​

Ví dụ 1: Performance Benchmark Tool ​

cpp
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <iomanip>
#include <functional>
using namespace std;

class PerformanceBenchmark {
private:
    mt19937 rng;
    
public:
    PerformanceBenchmark() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    
    // Generate test data
    vector<int> generateRandomData(size_t size, int minVal = 0, int maxVal = 10000) {
        vector<int> data;
        data.reserve(size);
        
        uniform_int_distribution<int> dist(minVal, maxVal);
        for (size_t i = 0; i < size; i++) {
            data.push_back(dist(rng));
        }
        
        return data;
    }
    
    vector<int> generateSortedData(size_t size) {
        vector<int> data = generateRandomData(size);
        sort(data.begin(), data.end());
        return data;
    }
    
    // Timing utility
    template<typename Func>
    chrono::microseconds timeFunction(Func&& func, const string& description = "") {
        auto start = chrono::high_resolution_clock::now();
        func();
        auto end = chrono::high_resolution_clock::now();
        
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        
        if (!description.empty()) {
            cout << description << ": " << duration.count() << " μs" << endl;
        }
        
        return duration;
    }
    
    // O(1) - Constant Time Examples
    void benchmarkConstantTime() {
        cout << "\n=== O(1) CONSTANT TIME OPERATIONS ===" << endl;
        
        vector<size_t> sizes = {1000, 10000, 100000, 1000000};
        
        for (size_t size : sizes) {
            vector<int> data = generateRandomData(size);
            
            auto duration = timeFunction([&]() {
                // Array access - always O(1)
                volatile int first = data[0];
                volatile int middle = data[size / 2];
                volatile int last = data[size - 1];
            }, "Size " + to_string(size));
        }
        
        cout << "✅ Notice: Time should remain roughly constant regardless of size" << endl;
    }
    
    // O(n) - Linear Time Examples
    void benchmarkLinearTime() {
        cout << "\n=== O(n) LINEAR TIME OPERATIONS ===" << endl;
        
        vector<size_t> sizes = {1000, 2000, 4000, 8000};
        
        for (size_t size : sizes) {
            vector<int> data = generateRandomData(size);
            int target = data[size * 3 / 4];  // Target likely to be found
            
            auto duration = timeFunction([&]() {
                // Linear search - O(n)
                for (size_t i = 0; i < data.size(); i++) {
                    if (data[i] == target) {
                        break;
                    }
                }
            }, "Size " + to_string(size));
        }
        
        cout << "✅ Notice: Time should roughly double when size doubles" << endl;
    }
    
    // O(log n) - Logarithmic Time Examples
    void benchmarkLogarithmicTime() {
        cout << "\n=== O(log n) LOGARITHMIC TIME OPERATIONS ===" << endl;
        
        vector<size_t> sizes = {1000, 10000, 100000, 1000000};
        
        for (size_t size : sizes) {
            vector<int> data = generateSortedData(size);
            int target = data[size / 2];
            
            auto duration = timeFunction([&]() {
                // Binary search - O(log n)
                binary_search(data.begin(), data.end(), target);
            }, "Size " + to_string(size));
        }
        
        cout << "✅ Notice: Time increases very slowly as size increases" << endl;
    }
    
    // O(n²) - Quadratic Time Examples
    void benchmarkQuadraticTime() {
        cout << "\n=== O(n²) QUADRATIC TIME OPERATIONS ===" << endl;
        
        vector<size_t> sizes = {100, 200, 400, 800};  // Smaller sizes for quadratic
        
        for (size_t size : sizes) {
            vector<int> data = generateRandomData(size);
            
            auto duration = timeFunction([&]() {
                // Bubble sort - O(n²)
                vector<int> temp = data;  // Copy for sorting
                int n = temp.size();
                
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n - i - 1; j++) {
                        if (temp[j] > temp[j + 1]) {
                            swap(temp[j], temp[j + 1]);
                        }
                    }
                }
            }, "Size " + to_string(size));
        }
        
        cout << "✅ Notice: Time should roughly quadruple when size doubles" << endl;
    }
    
    // O(n log n) - Linearithmic Time Examples
    void benchmarkLinearithmicTime() {
        cout << "\n=== O(n log n) LINEARITHMIC TIME OPERATIONS ===" << endl;
        
        vector<size_t> sizes = {1000, 2000, 4000, 8000};
        
        for (size_t size : sizes) {
            vector<int> data = generateRandomData(size);
            
            auto duration = timeFunction([&]() {
                // STL sort - O(n log n)
                vector<int> temp = data;  // Copy for sorting
                sort(temp.begin(), temp.end());
            }, "Size " + to_string(size));
        }
        
        cout << "✅ Notice: Time increases slightly more than linear but much less than quadratic" << endl;
    }
    
    // Space Complexity Examples
    void benchmarkSpaceComplexity() {
        cout << "\n=== SPACE COMPLEXITY EXAMPLES ===" << endl;
        
        size_t size = 10000;
        vector<int> data = generateRandomData(size);
        
        // O(1) Space
        timeFunction([&]() {
            int sum = 0;
            for (int x : data) {
                sum += x;  // Only using constant extra space
            }
        }, "O(1) Space - Sum calculation");
        
        // O(n) Space
        timeFunction([&]() {
            vector<int> copy = data;  // Creating copy uses O(n) space
            reverse(copy.begin(), copy.end());
        }, "O(n) Space - Array copy");
        
        // O(n²) Space
        timeFunction([&]() {
            int n = 100;  // Smaller size for demonstration
            vector<vector<int>> matrix(n, vector<int>(n, 0));
            
            // Fill matrix
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = i + j;
                }
            }
        }, "O(n²) Space - Matrix creation");
    }
    
    // Algorithm Comparison
    void compareSearchAlgorithms() {
        cout << "\n=== SEARCH ALGORITHM COMPARISON ===" << endl;
        
        size_t size = 100000;
        vector<int> data = generateSortedData(size);
        int target = data[size * 3 / 4];
        
        // Linear Search - O(n)
        timeFunction([&]() {
            for (size_t i = 0; i < data.size(); i++) {
                if (data[i] == target) break;
            }
        }, "Linear Search O(n)");
        
        // Binary Search - O(log n)
        timeFunction([&]() {
            binary_search(data.begin(), data.end(), target);
        }, "Binary Search O(log n)");
        
        cout << "✅ Binary search should be significantly faster for large datasets" << endl;
    }
    
    void compareSortingAlgorithms() {
        cout << "\n=== SORTING ALGORITHM COMPARISON ===" << endl;
        
        size_t size = 5000;
        vector<int> originalData = generateRandomData(size);
        
        // Bubble Sort - O(n²)
        {
            vector<int> data = originalData;
            timeFunction([&]() {
                int n = data.size();
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n - i - 1; j++) {
                        if (data[j] > data[j + 1]) {
                            swap(data[j], data[j + 1]);
                        }
                    }
                }
            }, "Bubble Sort O(n²)");
        }
        
        // Selection Sort - O(n²)
        {
            vector<int> data = originalData;
            timeFunction([&]() {
                int n = data.size();
                for (int i = 0; i < n - 1; i++) {
                    int minIdx = i;
                    for (int j = i + 1; j < n; j++) {
                        if (data[j] < data[minIdx]) {
                            minIdx = j;
                        }
                    }
                    swap(data[i], data[minIdx]);
                }
            }, "Selection Sort O(n²)");
        }
        
        // STL Sort (typically Introsort) - O(n log n)
        {
            vector<int> data = originalData;
            timeFunction([&]() {
                sort(data.begin(), data.end());
            }, "STL Sort O(n log n)");
        }
        
        cout << "✅ STL sort should be significantly faster than quadratic sorts" << endl;
    }
    
    void runAllBenchmarks() {
        cout << "🔬 ALGORITHM COMPLEXITY BENCHMARK SUITE" << endl;
        cout << "=======================================" << endl;
        
        benchmarkConstantTime();
        benchmarkLinearTime();
        benchmarkLogarithmicTime();
        benchmarkQuadraticTime();
        benchmarkLinearithmicTime();
        benchmarkSpaceComplexity();
        compareSearchAlgorithms();
        compareSortingAlgorithms();
        
        cout << "\n🎯 BENCHMARK COMPLETE!" << endl;
        cout << "Key Takeaway: Choose algorithms with better time complexity for large datasets!" << endl;
    }
};

int main() {
    cout << "=== ALGORITHM COMPLEXITY ANALYSIS DEMO ===" << endl;
    
    PerformanceBenchmark benchmark;
    benchmark.runAllBenchmarks();
    
    return 0;
}

Ví dụ 2: Complexity Analyzer Tool ​

cpp
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <functional>
#include <chrono>
#include <cmath>
using namespace std;

// Code complexity analyzer
class ComplexityAnalyzer {
private:
    struct ComplexityResult {
        string timeComplexity;
        string spaceComplexity;
        string description;
        vector<pair<size_t, double>> benchmarkData;
    };
    
public:
    // Analyze function complexity by running benchmarks
    template<typename Func>
    ComplexityResult analyzeComplexity(Func func, 
                                     const vector<size_t>& inputSizes,
                                     const string& functionName) {
        ComplexityResult result;
        result.description = "Analyzing: " + functionName;
        
        cout << "\n🔍 Analyzing " << functionName << "..." << endl;
        
        // Run benchmarks for different input sizes
        for (size_t size : inputSizes) {
            auto data = generateTestData(size);
            
            auto start = chrono::high_resolution_clock::now();
            func(data);
            auto end = chrono::high_resolution_clock::now();
            
            auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
            double timeMs = duration.count() / 1000.0;
            
            result.benchmarkData.push_back({size, timeMs});
            
            cout << "  Size " << size << ": " << timeMs << " ms" << endl;
        }
        
        // Analyze growth pattern
        result.timeComplexity = detectTimeComplexity(result.benchmarkData);
        result.spaceComplexity = "O(1)"; // Simplified for this example
        
        return result;
    }
    
private:
    vector<int> generateTestData(size_t size) {
        vector<int> data;
        data.reserve(size);
        for (size_t i = 0; i < size; i++) {
            data.push_back(rand() % 1000);
        }
        return data;
    }
    
    string detectTimeComplexity(const vector<pair<size_t, double>>& data) {
        if (data.size() < 2) return "Unknown";
        
        // Calculate growth ratios
        vector<double> ratios;
        for (size_t i = 1; i < data.size(); i++) {
            double sizeRatio = (double)data[i].first / data[i-1].first;
            double timeRatio = data[i].second / data[i-1].second;
            ratios.push_back(timeRatio / sizeRatio);
        }
        
        // Analyze pattern
        double avgRatio = 0;
        for (double ratio : ratios) {
            avgRatio += ratio;
        }
        avgRatio /= ratios.size();
        
        // Simple heuristics
        if (avgRatio < 1.2) {
            return "O(1) - Constant";
        } else if (avgRatio < 1.8) {
            return "O(log n) - Logarithmic";
        } else if (avgRatio < 2.5) {
            return "O(n) - Linear";
        } else if (avgRatio < 4.0) {
            return "O(n log n) - Linearithmic";
        } else {
            return "O(n²) or higher - Polynomial/Exponential";
        }
    }
    
public:
    void runComplexityAnalysis() {
        cout << "=== AUTOMATED COMPLEXITY ANALYSIS ===" << endl;
        
        vector<size_t> sizes = {100, 200, 400, 800, 1600};
        
        // Analyze different algorithms
        
        // O(1) - Array access
        auto constantResult = analyzeComplexity([](const vector<int>& data) {
            volatile int val = data[0]; // Prevent optimization
        }, sizes, "Array Access");
        
        // O(n) - Linear search
        auto linearResult = analyzeComplexity([](const vector<int>& data) {
            int target = data[data.size() / 2];
            for (size_t i = 0; i < data.size(); i++) {
                if (data[i] == target) break;
            }
        }, sizes, "Linear Search");
        
        // O(n²) - Bubble sort
        auto quadraticResult = analyzeComplexity([](vector<int> data) {
            int n = data.size();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n - i - 1; j++) {
                    if (data[j] > data[j + 1]) {
                        swap(data[j], data[j + 1]);
                    }
                }
            }
        }, sizes, "Bubble Sort");
        
        // Print results
        cout << "\n📊 ANALYSIS RESULTS:" << endl;
        cout << "Array Access: " << constantResult.timeComplexity << endl;
        cout << "Linear Search: " << linearResult.timeComplexity << endl;
        cout << "Bubble Sort: " << quadraticResult.timeComplexity << endl;
    }
};

int main() {
    ComplexityAnalyzer analyzer;
    analyzer.runComplexityAnalysis();
    
    return 0;
}

Ví dụ 3: Real-world Complexity Problems ​

cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <chrono>
using namespace std;

class RealWorldComplexity {
public:
    // Problem 1: Social Network - Friend Recommendations
    // Different approaches with different complexities
    
    // O(n²) - Naive approach: Check all pairs
    vector<string> findMutualFriendsNaive(const string& user,
                                         const unordered_map<string, vector<string>>& friendGraph) {
        vector<string> mutualFriends;
        
        if (friendGraph.find(user) == friendGraph.end()) return mutualFriends;
        
        const auto& userFriends = friendGraph.at(user);
        
        // For each friend of user
        for (const string& friend1 : userFriends) {
            if (friendGraph.find(friend1) == friendGraph.end()) continue;
            
            const auto& friend1Friends = friendGraph.at(friend1);
            
            // For each friend of friend1
            for (const string& friend2 : friend1Friends) {
                if (friend2 != user && 
                    find(userFriends.begin(), userFriends.end(), friend2) == userFriends.end()) {
                    // friend2 is not direct friend of user
                    if (find(mutualFriends.begin(), mutualFriends.end(), friend2) == mutualFriends.end()) {
                        mutualFriends.push_back(friend2);
                    }
                }
            }
        }
        
        return mutualFriends;
    }
    
    // O(n) - Optimized with hash map
    vector<string> findMutualFriendsOptimized(const string& user,
                                             const unordered_map<string, vector<string>>& friendGraph) {
        unordered_map<string, int> candidateCount;
        unordered_map<string, bool> directFriends;
        
        if (friendGraph.find(user) == friendGraph.end()) return {};
        
        const auto& userFriends = friendGraph.at(user);
        
        // Mark direct friends
        for (const string& friend : userFriends) {
            directFriends[friend] = true;
        }
        
        // Count mutual connections
        for (const string& friend : userFriends) {
            if (friendGraph.find(friend) == friendGraph.end()) continue;
            
            for (const string& friendOfFriend : friendGraph.at(friend)) {
                if (friendOfFriend != user && !directFriends[friendOfFriend]) {
                    candidateCount[friendOfFriend]++;
                }
            }
        }
        
        // Sort by connection count
        vector<pair<int, string>> recommendations;
        for (const auto& pair : candidateCount) {
            recommendations.push_back({pair.second, pair.first});
        }
        
        sort(recommendations.rbegin(), recommendations.rend());
        
        vector<string> result;
        for (const auto& rec : recommendations) {
            result.push_back(rec.second);
        }
        
        return result;
    }
    
    // Problem 2: E-commerce - Product Search
    
    // O(n) - Linear search through all products
    vector<string> searchProductsLinear(const vector<string>& products, const string& query) {
        vector<string> results;
        
        for (const string& product : products) {
            if (product.find(query) != string::npos) {
                results.push_back(product);
            }
        }
        
        return results;
    }
    
    // O(log n) average - Using indexed search (simplified)
    class ProductIndex {
    private:
        unordered_map<string, vector<string>> wordToProducts;
        
    public:
        void buildIndex(const vector<string>& products) {
            for (const string& product : products) {
                // Simple word extraction (space-separated)
                string word = "";
                for (char c : product + " ") {
                    if (c == ' ') {
                        if (!word.empty()) {
                            wordToProducts[word].push_back(product);
                            word = "";
                        }
                    } else {
                        word += tolower(c);
                    }
                }
            }
        }
        
        vector<string> search(const string& query) {
            string lowerQuery = query;
            transform(lowerQuery.begin(), lowerQuery.end(), lowerQuery.begin(), ::tolower);
            
            auto it = wordToProducts.find(lowerQuery);
            if (it != wordToProducts.end()) {
                return it->second;
            }
            return {};
        }
    };
    
    // Problem 3: Cache System - LRU Implementation
    
    // Different complexities for cache operations
    class LRUCache {
    private:
        struct Node {
            int key, value;
            Node* prev;
            Node* next;
            Node(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
        };
        
        unordered_map<int, Node*> cache;
        Node* head;
        Node* tail;
        int capacity;
        
        void addNode(Node* node) {
            node->prev = head;
            node->next = head->next;
            head->next->prev = node;
            head->next = node;
        }
        
        void removeNode(Node* node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        
        void moveToHead(Node* node) {
            removeNode(node);
            addNode(node);
        }
        
        Node* popTail() {
            Node* lastNode = tail->prev;
            removeNode(lastNode);
            return lastNode;
        }
        
    public:
        LRUCache(int cap) : capacity(cap) {
            head = new Node();
            tail = new Node();
            head->next = tail;
            tail->prev = head;
        }
        
        // O(1) - Constant time get
        int get(int key) {
            auto it = cache.find(key);
            if (it != cache.end()) {
                Node* node = it->second;
                moveToHead(node);
                return node->value;
            }
            return -1;
        }
        
        // O(1) - Constant time put
        void put(int key, int value) {
            auto it = cache.find(key);
            if (it != cache.end()) {
                Node* node = it->second;
                node->value = value;
                moveToHead(node);
            } else {
                Node* newNode = new Node(key, value);
                
                if (cache.size() >= capacity) {
                    Node* tail_node = popTail();
                    cache.erase(tail_node->key);
                    delete tail_node;
                }
                
                cache[key] = newNode;
                addNode(newNode);
            }
        }
    };
    
    void demonstrateComplexityImpact() {
        cout << "=== REAL-WORLD COMPLEXITY IMPACT ===" << endl;
        
        // Demo 1: Friend recommendations
        cout << "\n1. Social Network Friend Recommendations:" << endl;
        
        unordered_map<string, vector<string>> socialGraph = {
            {"Alice", {"Bob", "Charlie", "David"}},
            {"Bob", {"Alice", "Eva", "Frank"}},
            {"Charlie", {"Alice", "Grace", "Henry"}},
            {"David", {"Alice", "Ivan", "Jack"}},
            {"Eva", {"Bob", "Kate", "Liam"}},
            {"Frank", {"Bob", "Mary", "Nick"}},
            {"Grace", {"Charlie", "Oscar", "Paul"}},
            {"Henry", {"Charlie", "Quinn", "Ryan"}}
        };
        
        auto start = chrono::high_resolution_clock::now();
        auto recommendations = findMutualFriendsOptimized("Alice", socialGraph);
        auto end = chrono::high_resolution_clock::now();
        
        cout << "Recommendations for Alice: ";
        for (const string& rec : recommendations) {
            cout << rec << " ";
        }
        cout << endl;
        
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << "Time taken: " << duration.count() << " μs" << endl;
        
        // Demo 2: Product search
        cout << "\n2. E-commerce Product Search:" << endl;
        
        vector<string> products = {
            "iPhone 15 Pro Max",
            "Samsung Galaxy S24",
            "MacBook Pro 16 inch",
            "Dell XPS 13",
            "iPad Air",
            "Surface Pro 9",
            "AirPods Pro",
            "Sony WH-1000XM5"
        };
        
        ProductIndex index;
        index.buildIndex(products);
        
        start = chrono::high_resolution_clock::now();
        auto searchResults = index.search("Pro");
        end = chrono::high_resolution_clock::now();
        
        cout << "Search results for 'Pro': ";
        for (const string& result : searchResults) {
            cout << result << " | ";
        }
        cout << endl;
        
        duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << "Indexed search time: " << duration.count() << " μs" << endl;
        
        // Demo 3: Cache performance
        cout << "\n3. LRU Cache Performance:" << endl;
        
        LRUCache cache(3);
        
        start = chrono::high_resolution_clock::now();
        
        cache.put(1, 100);
        cache.put(2, 200);
        cache.put(3, 300);
        
        cout << "Get key 2: " << cache.get(2) << endl;
        
        cache.put(4, 400);  // Should evict key 1
        
        cout << "Get key 1: " << cache.get(1) << " (should be -1, evicted)" << endl;
        cout << "Get key 3: " << cache.get(3) << endl;
        
        end = chrono::high_resolution_clock::now();
        duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << "Cache operations time: " << duration.count() << " μs" << endl;
        
        cout << "\n🎯 Key Insight: Optimized algorithms make real difference in user experience!" << endl;
    }
};

int main() {
    RealWorldComplexity demo;
    demo.demonstrateComplexityImpact();
    
    return 0;
}

🏋️ Thực hành ​

Bài tập 1: Algorithm Time Complexity Analysis ​

Analyze time complexity của các functions sau:

cpp
// Function A
int mysteryA(vector<int>& arr) {
    int sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];
    }
    return sum;
}

// Function B  
void mysteryB(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[i] > arr[j]) {
                swap(arr[i], arr[j]);
            }
        }
    }
}

// Function C
int mysteryC(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Bài tập 2: Space Complexity Optimization ​

Optimize space complexity của function này:

cpp
// Original: O(n) space
vector<int> getEvenNumbers(const vector<int>& input) {
    vector<int> result;
    for (int num : input) {
        if (num % 2 == 0) {
            result.push_back(num);
        }
    }
    return result;
}

// TODO: Rewrite để achieve O(1) space complexity

Bài tập 3: Algorithm Selection Problem ​

Cho một ứng dụng cần perform các operations sau. Chọn data structure và algorithm tối ưu:

  • Insert new user: Frequent operation
  • Find user by ID: Most frequent operation
  • Update user info: Moderate frequency
  • Delete user: Rare operation
  • List all users: Very rare

Explain lựa chọn của bạn dựa trên complexity analysis.

Bài tập 4: Performance Bottleneck Detection ​

Analyze và optimize đoạn code sau:

cpp
vector<int> processData(const vector<vector<int>>& matrix) {
    vector<int> result;
    
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[i].size(); j++) {
            // Check if current element is local maximum
            bool isMax = true;
            for (int di = -1; di <= 1; di++) {
                for (int dj = -1; dj <= 1; dj++) {
                    int ni = i + di, nj = j + dj;
                    if (ni >= 0 && ni < matrix.size() && 
                        nj >= 0 && nj < matrix[ni].size()) {
                        if (matrix[ni][nj] > matrix[i][j]) {
                            isMax = false;
                            break;
                        }
                    }
                }
                if (!isMax) break;
            }
            if (isMax) {
                result.push_back(matrix[i][j]);
            }
        }
    }
    
    return result;
}

Lời giải chi tiết ​

Bài tập 1 - Time Complexity Analysis:

cpp
// Function A: O(n) - Linear Time
// Giải thích: Single loop qua tất cả n elements
int mysteryA(vector<int>& arr) {
    int sum = 0;
    for (int i = 0; i < arr.size(); i++) {  // n iterations
        sum += arr[i];  // O(1) operation
    }
    return sum;  // Total: O(n)
}

// Function B: O(n²) - Quadratic Time
// Giải thích: Nested loops, bubble sort pattern
void mysteryB(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {      // n iterations
        for (int j = i + 1; j < arr.size(); j++) { // up to n iterations
            if (arr[i] > arr[j]) {              // O(1) operation
                swap(arr[i], arr[j]);           // O(1) operation
            }
        }
    }
    // Total: O(n²)
}

// Function C: O(log n) - Logarithmic Time
// Giải thích: Binary search, eliminates half each iteration
int mysteryC(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {                    // log n iterations max
        int mid = (left + right) / 2;          // O(1) operation
        if (arr[mid] == target) return mid;    // O(1) operation
        else if (arr[mid] < target) left = mid + 1;  // Eliminate half
        else right = mid - 1;                  // Eliminate half
    }
    return -1;  // Total: O(log n)
}

Bài tập 2 - Space Optimization:

cpp
// Original O(n) space - creates new vector
vector<int> getEvenNumbers(const vector<int>& input) {
    vector<int> result;
    for (int num : input) {
        if (num % 2 == 0) {
            result.push_back(num);
        }
    }
    return result;
}

// Optimized O(1) space - in-place modification
void filterEvenNumbersInPlace(vector<int>& input) {
    int writeIndex = 0;
    
    // Move even numbers to front of array
    for (int readIndex = 0; readIndex < input.size(); readIndex++) {
        if (input[readIndex] % 2 == 0) {
            input[writeIndex++] = input[readIndex];
        }
    }
    
    // Resize to keep only even numbers
    input.resize(writeIndex);
}

// Alternative: Using iterators and STL
void filterEvenSTL(vector<int>& input) {
    input.erase(
        remove_if(input.begin(), input.end(), 
                  [](int x) { return x % 2 != 0; }),
        input.end()
    );
}

📋 Tóm tắt ​

Các điểm quan trọng ​

Big-O Hierarchy (tốt → tệ):

  • O(1): Constant - Hash table lookup
  • O(log n): Logarithmic - Binary search
  • O(n): Linear - Array traversal
  • O(n log n): Linearithmic - Efficient sorting
  • O(n²): Quadratic - Nested loops
  • O(2ⁿ): Exponential - Recursive fibonacci

Analysis Principles:

  • Focus on worst-case scenario
  • Ignore constant factors và lower-order terms
  • Consider both time và space complexity
  • Understand amortized analysis for dynamic structures

Common Patterns:

  • Single loop = O(n)
  • Nested loops = O(n²), O(n³)
  • Divide and conquer = O(log n) hoặc O(n log n)
  • Dynamic programming = O(n×m) cho 2D problems

Best Practices ​

Algorithm Selection:

  • Choose O(log n) over O(n) khi có thể
  • Use appropriate data structures (hash maps cho O(1) lookup)
  • Consider space-time tradeoffs
  • Profile real performance, không chỉ theoretical complexity

Optimization Strategies:

  • Avoid premature optimization - measure first
  • Cache frequently accessed data
  • Use efficient data structures cho specific use cases
  • Minimize nested loops khi có thể

Real-world Considerations:

  • Cache locality affects real performance
  • Input size distribution matters
  • Memory constraints có thể override time optimality
  • Maintenance costs của complex optimizations

Chuẩn bị cho bài tiếp theo ​

Bài học tiếp theo sẽ tìm hiểu về Sorting Algorithms - các thuật toán sắp xếp:

  • Simple Sorts: Bubble, Selection, Insertion sort
  • Efficient Sorts: Quick sort, Merge sort, Heap sort
  • Specialized Sorts: Counting sort, Radix sort
  • STL Sorting: std::sort, std::stable_sort, custom comparators
  • Performance Analysis: Khi nào dùng thuật toán nào

Complexity analysis là foundation cho hiểu performance và optimization. Master concepts này để viết efficient code!

Khóa học C++ miễn phí

Copyright © 2024 zukahai