从 O(1) 到 O(N)：程序员进阶路上必修的算法效率课！

Extreme35

发布于 2025-12-23 18:27:47

1580

文章被收录于专栏：DLDL

🏠 个人主页: EXtreme35

📚 个人专栏:

专栏名称	专栏主题简述
《C语言》	C语言基础、语法解析与实战应用
《数据结构》	线性表、树、图等核心数据结构详解
《题解思维》	算法思路、解题技巧与高效编程实践

前言作为一名“程序猿”，大家应该都听过这么一句话：程序=数据结构+算法。这句话是由瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年获得图灵奖时说的一句话，这位大佬还以这句话为名出了一本书《Algorithms + Data Structures=Programs》，从此这句话就成为了大家耳熟能详的一句名言。随着时间的推移，不管这句话是不是非常准确，但至少能说明数据结构与算法对程序来说是非常核心的基础，如果我们想要写出更多优秀优雅的代码，那么数据结构与算法是必须要掌握好的。

一、为什么要学习算法

很多人可能觉得，我不会算法，代码一样写得很"溜"，算法这东西似乎用处不大。现在互联网的发达，我们想要什么几乎都可以在网上找到现成的，各种框架功能十分强大，似乎看起来确实不用算法也可以写出“好代码”。然而假如我们不懂算法，比如项目中用到了排序，我们如何评估代码的执行效率？再比如最常用的 ArrayList 和 LinkedList，我们该如何选择，又比如说我们需要去集合中找某一个数，又该如何写出性能优秀的代码呢？

同样的代码，如何判断谁的代码是优秀的代码？可读性，可扩展性，健壮性可能都可以用来判定，然而这些东西我觉得并不能直接体现出你代码的优秀，因为对用户而言，访问你的代码响应速度快那就是优秀的代码，相反，动辄响应几秒甚至更长时间的接口，恐怕就算你可读性再好，再健壮也称不上是好代码。

所以说一段代码是否优秀，最直接的判断标准就是性能，而如果要写出高性能的代码，那么就必须要了解算法，而且抛开这个因素，但凡不想一辈子都写 CRUD 代码的，也需要去了解算法，我们使用的很多框架和中间件底层都有数据结构和算法的身影，学好算法对我们源码阅读时理解其设计思想也是大有裨益的。

要说功利性的目的，那就是面试，目前很多大厂的面试，算法基本必面，所以想进大厂的话，咱们也得好好学学算法。

二、算法的效率报告

当你开始学习算法时，你一定想知道：我写的代码到底快不快？

想象一下，你写了两种不同的代码来解决同一个问题。你想知道哪一个效率更高，于是你运行了一下，发现第一个程序运行了 5 秒，第二个只运行了 0.5 秒。所以第二个程序更快？

别急着下结论！这个简单的计时方法，就像是给算法做了一个不靠谱的体检。

2.1 为什么直接计时不科学？

在计算机科学中，我们衡量一个算法的好坏，通常从两个维度来衡量：时间和空间。

但我们为什么不直接用秒表来计时呢？原因很简单，程序的实际运行时间会受到很多外部因素的影响：

硬件配置： 你在老旧电脑上跑 10 秒的代码，换到一台高性能服务器上可能瞬间完成。同一个算法程序，用一个低配置机器和新高配置机器，运行时间也不同。
编程语言和编译器： 不同的编译器编译出来的指令条数可能不一样。同一个算法程序，用一个老编译器进行编译和新编译器编译，在同样机器下运行时间不同。
数据规模： 运行时间会随着输入数据的增大而变化。
程序写好后才能测试： 时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

直接计时无法脱离具体的编译和运行环境，也无法在写程序前进行理论评估。

为了更科学、更公平地评估算法效率，我们引入了一个概念：时间复杂度。

2.2 什么是时间复杂度？

时间复杂度是一个函数式

T(N)

，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率。这个

T(N)

并不是指秒，而是指程序中基本操作执行的次数。

简单来说，我们不再数“秒”，而是数步。

算法程序被编译后生成二进制指令，程序运行，就是CPU执行这些编译好的指令。我们通过程序代码或者理论思想计算出程序的执行次数的函数式

T(N)

。假设每句指令执行时间基本一样，那么执行次数和运行时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。

案例分析：计算执行次数

T(N)

来看一段代码片段（假设它是一个函数

Func1(N)

）：

void Func1(int N) {
    int count = 0; 
    for (int i = 0; i < N; ++i) { 
        for (int j = 0; j < N; ++j) { 
            ++count; 
        }
    }
    for (int k = 0; k < 2 * N; ++k) { 
        ++count; 
    }
    int M = 10; 
    while (M--) { 
        ++count; 
    }
}

这段代码中所有基本操作的精确执行次数函数

T(N)

可以粗略地写为：

T(N) = N^2 + 2N + 10

当我们取不同的

N

值时，可以看到

N^2

对结果的影响最大：

N=10

，

T(N)=130

N=100

，

T(N)=10210

N=1000

，

T(N)=1002010

通过对

N

取值分析，对结果影响最大的一项是

N^2

。当

N

变得非常大时，常数项和低阶项对结果的影响很小。

2.3 算法效率的身份证：大

O

表示法

在实际计算时间复杂度时，我们不追求精确的执行次数。我们更关心的是当

N

不断变大时，执行次数的增长趋势（增长量级）。复杂度的表示通常使用大

O

渐进表示法。因此，我们使用**大

O

渐进表示法（Big O notation）**来描述这种渐进行为。

推导大

O

阶的 3 个规则

要从

T(N)

推导出

O(N)

，只需遵循以下三个步骤：

只保留最高阶项： 去掉那些低阶项，因为当

N

不断变大时，低阶项对结果影响越来越小，当

N

趋于无穷大时，就可以忽略不计了。

去除最高阶项的常数系数： 如果最高阶项存在且不是 1，则去除这个项目的常数系数，因为当

N

不断变大，这个系数对结果影响越来越小，当

N

趋于无穷大时，就可以忽略不计了。

常数项用 1 取代：

T(N)

中如果没有

N

相关的项目，只有常数项，用常数 1 取代所有加法常数。

应用示例：

对于

T(N) = N^2 + 2N + 10

，

保留最高阶项：

N^2

去除系数（系数为 1，不变）：

N^2

最终时间复杂度为：

O(N^2)

对于

T(N) = 2N + 10

，

保留最高阶项：

2N

去除系数 2：

N

最终时间复杂度为：

O(N)

2.4 常见的时间复杂度示例

大 O O O 复杂度	名称	描述/增长趋势	代码示例
O ( 1 ) O(1) O(1)	常数阶	无论数据规模 N N N 多大，执行次数都是固定的常数。最快！	顺序执行的语句。例如 F u n c 4 Func4 Func4 中，循环 100 次，其 T ( N ) = 100 T(N)=100 T(N)=100，因此时间复杂度为 O ( 1 ) O(1) O(1)。
O ( log ⁡ N ) O(\log N) O(logN)	对数阶	执行次数随着 N N N 的增大，增长非常缓慢。	函数 func5 中，cnt 每次乘以 2，直到大于 N N N，执行次数 x x x 满足 2 x = N 2^x=N 2x=N，因此 x = log ⁡ 2 N x = \log_2 N x=log2N，时间复杂度为 O ( log ⁡ 2 n ) O(\log_2 n) O(log2n)，通常简写为 O ( log ⁡ n ) O(\log n) O(logn)。
O ( N ) O(N) O(N)	线性阶	执行次数与 N N N 成正比。	单层循环（遍历数组、链表）。例如阶乘递归 F a c ( N ) Fac(N) Fac(N) 会调用 N N N 次，时间复杂度为 O ( N ) O(N) O(N)。
O ( N log ⁡ N ) O(N \log N) O(NlogN)	线性对数阶	相当于 N N N 次对数操作。	优秀的排序算法（如归并排序的平均情况）。
O ( N 2 ) O(N^2) O(N2)	平方阶	执行次数是 N N N 的平方。	双重循环。例如冒泡排序的最坏情况执行次数为 N ( N + 1 ) 2 \frac{N(N+1)}{2} 2N(N+1)，时间复杂度取最差情况为 O ( N 2 ) O(N^2) O(N2)。
O ( 2 N ) O(2^N) O(2N)	指数阶	效率极低，程序性能会急剧恶化。

O

复杂度名称描述/增长趋势代码示例

O(1)

常数阶无论数据规模

N

多大，执行次数都是固定的常数。最快！顺序执行的语句。例如

Func4

中，循环 100 次，其

T(N)=100

，因此时间复杂度为

O(1)

。

O(\log N)

对数阶执行次数随着

N

的增大，增长非常缓慢。函数 func5 中，cnt 每次乘以 2，直到大于

N

，执行次数

x

满足

2^x=N

，因此

x = \log_2 N

，时间复杂度为

O(\log_2 n)

，通常简写为

O(\log n)

。

O(N)

线性阶执行次数与

N

成正比。单层循环（遍历数组、链表）。例如阶乘递归

Fac(N)

会调用

N

次，时间复杂度为

O(N)

。

O(N \log N)

线性对数阶相当于

N

次对数操作。优秀的排序算法（如归并排序的平均情况）。

O(N^2)

平方阶执行次数是

N

的平方。双重循环。例如冒泡排序的最坏情况执行次数为

\frac{N(N+1)}{2}

，时间复杂度取最差情况为

O(N^2)

。

O(2^N)

指数阶效率极低，程序性能会急剧恶化。

最好、最坏和平均情况

有些算法（比如查找和排序）的执行次数会根据输入数据的不同而变化。

最好情况

O(1)

：任意输入规模的最小运行次数（下界）。例如 strchr 查找字符，若要查找的字符在字符串第一个位置，则

T(N)=1

，时间复杂度为

O(1)

。

最坏情况

O(N)

：任意输入规模的最大运行次数（上界）。例如 strchr 查找字符，若要查找的字符在字符串最后一个位置，则

T(N)=N

，时间复杂度为

O(N)

。

平均情况： 任意输入规模的期望运行次数。

大

O

渐进表示法在实际中一般情况关注的是算法的上界，也就是最坏运行情况。

2.5 简单提一下空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。

空间复杂度算的是变量的个数，而不是程序占用了多少 bytes 的空间。它也使用大

O

渐进表示法。

你需要关注的是函数在运行时候显式申请的额外空间。函数运行时所需要的栈空间（存储参数、局部变量等）在编译期间已经确定好了。

O(1)

(常数空间)： 算法只使用了有限个额外的局部变量。例如冒泡排序

BubbleSort

额外申请了 exchange 等有限个局部变量，使用了常数个额外空间，因此空间复杂度为

O(1)

。

O(N)

(线性空间)： 算法所需的额外空间与输入规模

N

成正比。例如阶乘递归

Fac

调用了

N

次，额外开辟了

N

个函数栈帧，每个栈帧使用了常数个空间，因此空间复杂度为

O(N)

。

总结： 在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，存储容量已经很高，所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.6 总结与下一步

时间复杂度就是算法的“执行步数”，它帮我们脱离硬件和环境，用一种数学化的方式来衡量算法的效率。掌握大

O

表示法及其推导规则，是学习数据结构和算法的第一步，也是校招笔试面试的必考内容。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-23，如有侵权请联系 cloudcommunity@tencent.com 删除

程序员

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度