时间复杂度与空间复杂度 - C++ 数据结构与算法

← 返回课程C++ 数据结构与算法 › 第 1 关

进度 0%

第 1 关：时间复杂度与空间复杂度

C++进阶

📖 本课目标

本关属于《C++ 数据结构与算法》第 1 课。阅读右侧代码模板，理解每一行的作用，然后动手修改并完成练习。

🎯 本课要点

include <iostream>
include <chrono>

🛠 学习方式

阅读右侧代码模板中的注释与实现
修改代码，尝试达成新的效果
点击「运行」查看实际输出
确认理解后点击「提交」标记本关完成

💡 说明

本关为 C++，浏览器内无法真正执行该语言。当前「运行」输出为演示结果，请在本地环境中编译运行以验证代码。

main.pytest.py

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

// O(1) 常数时间
int constantTime(int n) {
    return n * 2;
}

// O(n) 线性时间
long long linearTime(int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += i;
    }
    return sum;
}

// O(n^2) 平方时间
long long quadraticTime(int n) {
    long long count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

int main() {
    int n = 10000;
    
    auto start = high_resolution_clock::now();
    constantTime(n);
    auto end = high_resolution_clock::now();
    cout << "O(1): " << duration_cast<microseconds>(end - start).count() << " μs" << endl;
    
    start = high_resolution_clock::now();
    linearTime(n);
    end = high_resolution_clock::now();
    cout << "O(n): " << duration_cast<microseconds>(end - start).count() << " μs" << endl;
    
    n = 1000;
    start = high_resolution_clock::now();
    quadraticTime(n);
    end = high_resolution_clock::now();
    cout << "O(n²): " << duration_cast<microseconds>(end - start).count() << " μs" << endl;
    
    return 0;
}

点击「运行」或「提交代码」查看结果

📖 查看本课说明

第 1 关：时间复杂度与空间复杂度

C++ · 进阶 · 《C++ 数据结构与算法》

include <iostream>
include <chrono>

本关为 C++，浏览器无法真正编译运行，请在本地环境验证代码。