跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客工具镜像开源精选AI社区
我的书AI 学习话题UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C算法

深入理解数据结构中的时间与空间复杂度

详细阐述了数据结构中时间与空间复杂度的概念及计算方法。通过大 O 渐进表示法规则,分析了常数阶、线性阶、平方阶、对数阶及递归函数的时间复杂度推导过程。同时探讨了空间复杂度的评估标准,结合冒泡排序与数组反置案例,说明了如何在实际代码中识别额外空间占用。内容涵盖 C 语言代码示例,修正了原有语法错误,旨在帮助开发者准确评估算法性能。

字节跳动发布于 2026/3/15更新于 2026/11/19102 浏览
深入理解数据结构中的时间与空间复杂度

时间复杂度与空间复杂度

评估一个算法的优劣,核心在于两个维度:时间和空间。时间复杂度衡量算法运行的快慢,空间复杂度则关注运行过程中额外占用的存储空间。

一、时间复杂度基础

算法的时间复杂度通常表示为函数 T(N),代表基本操作的执行次数。需要注意的是,不同编译器编译所需时间会有差异,新编译器通常更快,但这不影响我们分析算法本身的逻辑效率。

比较 T(N) = N 和 T(N) = N^2 时,显然前者在数据量增大时表现更优。

大 O 渐进表示法

为了简化分析,我们遵循以下规则推导大 O 阶:

  1. 保留最高阶项:当 N 趋于无穷大时,低阶项影响微乎其微,直接忽略。
  2. 去除常数系数:如果最高阶项是线性函数(如 5N),去掉系数 5,只保留 N。
  3. 常数项归一:如果没有 N 相关项,仅含常数,统一用 1 取代。
示例分析
void Func1(int N) {
    int count = 0;
    // 嵌套循环,执行 N*N 次
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            ++count;
        }
    }
    // 线性循环,执行 2*N 次
    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }
    // 常数循环,执行 10 次
    int M = 10;
    while (M--) {
        ++count;
    }
}

Func1 的基本操作次数为 T(N) = N² + 2N + 10。根据规则,保留最高阶项 N²,因此时间复杂度为 O(N²)。

常见复杂度对比

表达式大 O 表示类型
5201314O(1)常数阶
3n+4O(n)线性阶
3n²+4n+5O(n²)平方阶
3log₂n+4O(log n)对数阶
2ⁿO(2ⁿ)指数阶

二、典型场景解析

1. 常数阶 O(1)

无论输入规模如何,操作次数固定。

#include<stdio.h>
int main() {
    int x = 0;
    scanf("%d", &x); // 修正了原稿拼写错误 scnaf -> scanf
    printf("%d", x);
    return 0;
}

执行次数恒定为 3 次,复杂度 O(1)。

2. 线性阶 O(N)

操作次数随 N 线性增长。

void Func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }
    int M = 10;
    while (M--) {
        ++count;
    }
    printf("%d\n", count);
}

总次数 2N + 10,去低阶和系数后为 O(N)。

若存在两个独立变量 M 和 N:

void Func3(int N, int M) {
    int count = 0;
    for (int k = 0; k < M; ++k) ++count;
    for (int k = 0; k < N; ++k) ++count;
    printf("%d\n", count);
}

总次数 M + N。若 M 和 N 同阶,则为 O(N);若差异巨大,则取较大者。

3. 平方阶 O(N²)

嵌套循环的典型特征。

#include<stdio.h>
int main() {
    int x = 0;
    int begin = clock();
    int n = 100000;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            x++;
        }
    }
    int end = clock();
    printf("%dms\n", end - begin);
    return 0;
}

注意:此处需包含 <time.h> 头文件才能使用 clock()。双重循环导致复杂度为 O(N²)。

4. 对数阶 O(log N)

每次迭代将问题规模减半。

void func5(int n) {
    int cnt = 1;
    while (cnt < n) {
        cnt *= 2;
    }
}

设执行次数为 x,则 2^x = n,解得 x = log₂n。最坏情况复杂度为 O(log₂n)。

5. 递归函数

递归的时间复杂度取决于调用次数与单次调用的开销。

单递归示例:

long long Fac(size_t N) {
    if (N == 0) return 1; // 修正了原稿逻辑错误,增加基准条件
    return Fac(N-1) * N;
}

每次调用耗时 O(1),共调用 N 次,总复杂度 O(N)。

双递归示例: 若递归内部包含循环或多次递归调用,复杂度会显著上升。例如斐波那契数列的朴素递归实现,其时间复杂度接近 O(2^N),因为存在大量重复计算。

三、空间复杂度

空间复杂度衡量算法运行时临时占用的存储空间大小,同样使用大 O 表示法。在实际开发中,时间复杂度往往比空间复杂度更受关注,但在嵌入式等内存受限场景下,空间复杂度至关重要。

需注意:函数栈帧(参数、局部变量)通常在编译期确定,空间复杂度主要看运行时显式申请的空间。

冒泡排序 O(1)

void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end) {
        int exchange = 0; // 仅使用了有限个局部变量
        for (size_t i = 1; i < end; ++i) {
            if (a[i-1] > a[i]) {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0) break;
    }
}

除输入数组外,仅使用了常数个额外变量,空间复杂度为 O(1)。

数组反置 O(N)

void reverse(int* nums, int left, int right) {
    while (left < right) {
        int temp = nums[left]; // 修正变量名 tap -> temp
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

int main() {
    int nums[] = { 1,2,3,4,5,6,7 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int k = 0;
    scanf("%d", &k);
    k %= numsSize;
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

此例中虽然创建了数组,但这是输入数据本身。若算法内部需要创建与 N 等大的辅助数组,空间复杂度则为 O(N)。通常情况下,空间复杂度多为 O(1)、O(N) 或 O(N²),实际优化时仍以时间复杂度为首要考量。

目录

  1. 时间复杂度与空间复杂度
  2. 一、时间复杂度基础
  3. 大 O 渐进表示法
  4. 示例分析
  5. 常见复杂度对比
  6. 二、典型场景解析
  7. 1. 常数阶 O(1)
  8. 2. 线性阶 O(N)
  9. 3. 平方阶 O(N²)
  10. 4. 对数阶 O(log N)
  11. 5. 递归函数
  12. 三、空间复杂度
  13. 冒泡排序 O(1)
  14. 数组反置 O(N)

更多推荐文章

查看全部
  • LazyLLM 低代码框架实战:构建代码专家智能体
  • 2026 RAG 技术路线:基于 DeepSeek 与 Neo4j 知识图谱构建企业智能体系
  • Qwen3-VL 与 Qwen2-VL 对比:视觉感知升级实战评测
  • Neo4j 与 RDF 数据互操作:neosemantics 插件配置与 JSON-LD 实战
  • Stable Diffusion 整合包安装及基础使用教程
  • C++11 右值引用与移动语义详解:从性能瓶颈到零拷贝优化
  • Vivado FPGA 逻辑设计实战:同步 FIFO 全流程解析
  • 基于 SpringBoot 与 Vue 的流浪宠物管理系统设计与实现
  • A2UI 技术原理深度解析:AI Agent 如何安全生成富交互 UI
  • Android Studio 集成 Gemini AI 编程辅助指南
  • 扩散模型技术演进:从 DDPM 到 Stable Diffusion 再到 DiT
  • 小厂架构师 AI Agent 落地实战:从全能幻想到最小可用场景
  • Hookshot:轻量级 GitHub Webhook 处理工具
  • 基于 Python 与 AI Agent 的 Prompt 驱动零规则爬虫系统
  • Flutter Web 开发:解决跨域(CORS)问题指南
  • 图灵奖得主对人工智能发展的深远影响
  • 智能家居插件管理技术解析:HACS 优化方案与实践
  • VS Code 插件搭建 AI 开发环境完全指南
  • Spatial Joy 2025 全球 AR&AI 开发大赛参赛指南与资源详解
  • 渗透测试入门指南:定义、策略与方法

相关免费在线工具

  • 加密/解密文本

    使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online

  • Markdown转HTML

    将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online