大O表示法

|
#include <iostream>
#include <vector>
using namespace std;
 
// 函数A：计算数组和
int sumArray(const vector<int>& arr)
{
    int sum = 0;
    for (int i = 0; i < arr.size(); i++) // 循环 n 次
    {
        sum += arr[i]; // 每次循环执行常数时间操作
    }
    return sum;
}
// 时间复杂度：O(n)
// 原因：循环执行 n 次，每次循环是常数时间操作
// 就像把书从头翻到尾，需要翻 n 页
 
// 函数B：神秘函数
void mysteryFunction(int n)
{
    for (int i = 1; i < n; i *= 2) // 注意 i 每次乘以 2
    {
        cout << i << " ";
    }
}
// 时间复杂度：O(log n)
// 原因：循环变量每次乘以 2（1, 2, 4, 8, 16...）
// 需要 log₂(n) 次循环才能达到 n
// 就像切蛋糕每次切一半，切 log₂(n) 次就切完了
 
int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5 };
    cout << "数组和: " << sumArray(arr) << endl;
 
    cout << "MysteryFunction(16): ";
    mysteryFunction(16); // 输出: 1 2 4 8
    cout << endl;
    
    return 0;
}

|
数组和: 15
MysteryFunction(16): 1 2 4 8

|
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;
 
// 版本1：递归版本（无记忆化）- 时间复杂度 O(2ⁿ)
long long fibonacciRecursive(int n)
{
    if (n <= 1) return n;
    // 问题：会重复计算大量子问题
    // 例如：fib(5) = fib(4) + fib(3)
    //      fib(4) = fib(3) + fib(2)
    //      fib(3) = fib(2) + fib(1)
    // 可以看到 fib(3) 和 fib(2) 被重复计算了
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
 
// 版本2：动态规划版本 - 时间复杂度 O(n)
long long fibonacciDP(int n)
{
    if (n <= 1) return n;
    
    // 用数组记录已计算的值，避免重复计算
    vector<long long> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}
 
int main()
{
    // 测试小数值
    cout << "计算 fibonacci(10):" << endl;
    auto start1 = high_resolution_clock::now();
    long long result1 = fibonacciRecursive(10);
    auto end1 = high_resolution_clock::now();
    auto duration1 = duration_cast<milliseconds>(end1 - start1);
    cout << "递归版本: " << result1 << ", 耗时: " << duration1.count() << "ms" << endl;
 
    auto start2 = high_resolution_clock::now();
    long long result2 = fibonacciDP(10);
    auto end2 = high_resolution_clock::now();
    auto duration2 = duration_cast<milliseconds>(end2 - start2);
    cout << "动态规划版本: " << result2 << ", 耗时: " << duration2.count() << "ms" << endl;
 
    // 测试较大值（递归版本会很慢）
    cout << "\n计算 fibonacci(40):" << endl;
    auto start3 = high_resolution_clock::now();
    long long result3 = fibonacciDP(40);
    auto end3 = high_resolution_clock::now();
    auto duration3 = duration_cast<milliseconds>(end3 - start3);
    cout << "动态规划版本: " << result3 << ", 耗时: " << duration3.count() << "ms" << endl;
    
    cout << "\n注意：递归版本计算 fibonacci(40) 可能需要几分钟甚至更久！" << endl;
    cout << "这是因为递归版本的时间复杂度是指数级的 O(2ⁿ)" << endl;
    
    return 0;
}