chapter_computational_complexity/time_complexity/

[giscus[bot]]

chapter_computational_complexity/time_complexity/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_computational_complexity/time_complexity/

[euyia]

[krahets]

大佬好！那我猜测，力扣的通过线应该是根据复杂度定的；cf 是通过其他方式？这块我不太懂。
您提及问题可以约化为 “如何预估题目能够接受的复杂度范围” ，是个很好的主题，有空我会补上，或者您也可以来提交 Pull Reqest 完善本章内容，谢谢！

[euyia]

感谢回答 orz

[Zgaorong]

本页中n^2的讲解中，以「冒泡排序」为例，外层循环n-1 次，内层循环···次，平均为n/2次，因此时间复杂度为 ··· 。在这里计算的是最差时间复杂度，是不是描述应该为计算内层冒泡排序次数的等差数列求和，而不是平均n/2再乘以外层（n-1）的描述，感觉容易造成歧义。

[krahets]

哈喽，感谢反馈！等差数列求和的计算公式就是”数量 * 平均值“呀，也就是”外层循环数 * 内层平均值“

[Zgaorong]

啊这样，我读完直观觉得是找这个循环次数平均值了，然后再乘外部循环次数，就感觉到是去找了平均的复杂度。

[SSSDNSY]

最差 O 平均 θ 最优 Ω

[GaochaoZhu]

大佬好，界面是不是加一个“返回顶部”的按钮会更方便些呀；
例如本章节，对于小白来说，需要思考的地方比较多，看一遍感觉消化不了，想返回去再看一遍，需要鼠标滚动咔咔往上翻，有个“返回顶部”的话会更方便些。

[krahets]

谢谢建议，已加～

[jasontan1985]

大佬你好，我是一个算法小白，在看公式时就有了困难，比如这个公式T(n）= 3 +２ｎ，文中也没有具体写是怎么推导出来的，不仅如此，其他公式的推导好像也没有太详细。不知我是不是还该继续看下去。

[krahets]

哈喽，T(n) = 3 + 2n 的来源就是底下那串代码，前三行是 3 ，后面那个循环是 2n 。

void algorithm(int n) {
    int a = 1;  // +1
    a = a + 1;  // +1
    a = a * 2;  // +1
    // 循环 n 次
    for (int i = 0; i < n; i++) { // +1（每轮都执行 i ++）
        System.out.println(0);    // +1
    }
}

这部分的公式应该比较基础，可以尝试多看几遍，结合上下文啃一下。如果实在看不懂，那么可以先理解与公式无关的部分，比如复杂度的含义、常见复杂度类型以及对应的代码。加油噢！

[lqs-blog]

大佬，为什么是2n不是n,下面的for不是只循环了n次嘛

[krahets]

大佬，为什么是2n不是n,下面的for不是只循环了n次嘛

Hi @lqs-blog , 因为我们将 for 循环里的 i++ 也看作一次操作，这样一轮循环包含 2 个操作，可以看下右边的注释，+1 代表这行包含一个操作。

其实严格说来 for 循环里面，每轮还至少包含一个 i < n 的判断操作，每轮都会执行，但是这里为简便起见省略掉了。

[lqs-blog]

懂了，谢谢大佬^_^

[tadpole145]

/* 指数阶（递归实现） */
int expRecur(int n) {
    if (n == 1) return 1;
    return expRecur(n - 1) + expRecur(n - 1) + 1;
}

指数阶, 那个代码里面应该是 return expRecur(n - 2) + expRecur(n - 1) + 1吧;

[krahets]

哈喽，expRecur(n - 1) + expRecur(n - 1) 与图中的递归树对应，代表着一分为二，例如细胞分裂。

expRecur(n - 2) + expRecur(n - 1) 也是指数阶，代表斐波那契数列，你可以尝试画下递归树，和文中的做下对比～

[tadpole145]

感谢大佬

[Gonglja]

哈喽，k大，worst_best_time_complexity.cpp 代码编译时出错
环境：Ubuntu 20.04.5 LTS
g++ 版本：g++ (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

➜  chapter_computational_complexity git:(master g++ worst_best_time_complexity.cpp 
worst_best_time_complexity.cpp: In function ‘std::vector<int> randomNumbers(int)’:
worst_best_time_complexity.cpp:17:21: error: ‘chrono’ has not been declared
   17 |     unsigned seed = chrono::system_clock::now().time_since_epoch().count();
      |                     ^~~~~~
worst_best_time_complexity.cpp:19:5: error: ‘shuffle’ was not declared in this scope
   19 |     shuffle(nums.begin(), nums.end(), default_random_engine(seed));
      |     ^~~~~~~

原因是在 ../include/include.hpp中没有包含对应的头文件，

• std::chrono 在 #include 中
• std::shuffle 函数在 #include 中

添加后编译通过，运行正常

➜  chapter_computational_complexity git:(master g++ worst_best_time_complexity.cpp -o worst_best_time_complexity
➜  chapter_computational_complexity git:(master ls worst_best_time_complexity*                                  
worst_best_time_complexity  worst_best_time_complexity.cpp

[krahets]

看来 C++ 不同编译器的适配也需要单独做一下，谢谢！

[Gonglja]

应该是不需要的，c++ 中包含 std::chrono， 是c++ 的一个组件库，https://en.cppreference.com/w/cpp/chrono/duration

在用时需要将其包含进来，其它编译器不需要包含可能是默认编译链中其它的头文件中包含了改项（猜测），algorithm 类似

有没有其它编译器，可以看一下

[Gonglja]

暂时不需要，我用的 linux 下的不需要适配

如果后面有问题可以提 issue

[krahets]

了解，可能少数编译器需要显式地引入组件库，如果使用人数比较多，我们还是将其显式地 include 进来～

[2030028088]

看不明白，这章好像只是知道了时间复杂度的表示方式。

[krahets]

哈喽，除了表示方式外，本章还介绍了概念、推算方法、常见复杂度示例。

[lzy246617]

/* 指数阶（循环实现） */
int exponential(int n) {
    int count = 0, base = 1;
    // cell 每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < base; j++) {
            count++;
        }
        base *= 2;
    }
    // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count;
}

[lzy246617]

大佬，我的理解是这里第二个循环的操作与n无关，要省略。然后时间复杂度就是O(n)，但是文中是O(2^n)。不是很理解，求解！感谢

[krahets]

Hi! 第二个循环数量为 base ，而 base 的大小是由 n 来决定的，即 base = 2^i，变量 i 从 0 迭代至 n - 1

[lzy246617]

感谢大佬！！

[Tttobi4s]

K神，阶乘阶的操作总数应该不是等于最底层结点数量吧，是所有结点中的操作总数之和吗？

[krahets]

是的，操作总数是所有结点数量，每个结点代表一个被开启的递归方法。
本文中统计的是全排列的“方案数量”，对应最底层结点数量。

具体地，在 n = 0 时 返回 1 ，代表一个“排列方案”，通过回溯求和，最终得到的就是全排列的方案数。

[Tttobi4s]

好的，我明白了。谢谢K神！

[KaelInvoker]

指数阶这段没看懂count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1。为什么最后等于2^n - 1

[krahets]

等比数列求和公式 $a_1 * (1 - q^{n-1}) / (1-q)$ ，在这里 $a_1 = 1, q = 2$

[tauhuang]

等比求和公式是不是前面括号指数n多减了1

[guhulook]

对

[abigail22222]

能看到这本书真的太好了

[dkout-alt]

我不太清楚是不是我的系统问题，这两天一直在看，前几天似乎没问题。今天起的教程似乎所有显示数学公式的地方都出了问题？比如2.2.4中的一段变成了这样：

以下示例展示了使用上述技巧前、后的统计结果。
[ \begin{aligned} T(n) & = 2n(n + 1) + (5n + 1) + 2 & \text{完整统计 (-.-|||)} \newline & = 2n^2 + 7n + 3 \newline T(n) & = n^2 + n & \text{偷懒统计 (o.O)} \end{aligned} ]

Edge 和 Chrome 都有这样的显示问题

[krahets]

Hi 数学公式没有正常渲染，尝试换一个网络环境看看～比如在手机上看看正常不

[XXuQ]

学习数据结构画图太重要了，作者的图画的太棒啦，可以知道是什么软件画的吗

[krahets]

谢谢！Keynote Powerpoint 都可以画

[fallenleavesguy]

/* 指数阶（递归实现） */
function expRecur(n: number): number {
    if (n == 1) return 1;
    return expRecur(n - 1) + expRecur(n - 1) + 1;
}

这是在求什么，为什么最后要+1。没懂这里，谢谢。如果不要+1应该是求最后一层树结点数量，再+1就不知道是求什么了。请问是我理解错了吗?能不能分析一下这个函数的复杂度，谢谢大佬。已经理解了，是求全部节点数量，即操作次数，没毛病。谢谢大佬。太巧妙了。

---

总结为：n层的总节点数是n-1层总结点数*2 + 1,第1层总数为1，所以可以这样递归写。
也可总结为：第n层的总数=n-1层总数+1，所以n层总数为n-1层总数 + 第n层, 即: expRecur(n-1) + (expRecur(n-1) + 1)

看完gpt的答案我也懂了，感觉可以参考gpt的回答改进一下。
答案来自chatgpt:

---

上述函数的时间复杂度为指数阶（Exponential Time），记作O(2^n)。

在函数中，每次递归调用expRecur(n - 1)会导致另外两次递归调用，因此函数的递归深度将以指数级增长。每次递归调用的时间复杂度是常数级的，但由于递归的次数是指数级的，因此整体时间复杂度也是指数级的。

简单来说，随着输入n的增加，函数的执行时间将指数增长，导致非常低效。因此，这是一个效率较低的实现，特别是在处理大型输入时。如果需要更高效的实现，可以考虑使用其他算法或优化技巧来减少递归的次数。

[NuyoahCh]

常数阶的操作数量与输入数据大小无关，即不随着的变化而变化。

在以下函数中，尽管操作数量 size 可能很大，但由于其与输入数据大小无关，因此时间复杂度仍为 ：

其实在一些例子的选取上就能看到作者真的蛮用心的～ 感谢

https://www.hello-algo.com/chapter_computational_complexity/time_complexity/#2

[krahets]

谢谢鼓励！

[LCRltt]

可视化看不了

[krahets]

目前挂了，请耐心等待 pythontutor 修复

[zwdzzs1]

有点小问题，2.3.2这里把循环本身也算一次操作

def algorithm(n: int):
    a = 1      # +1
    a = a + 1  # +1
    a = a * 2  # +1
    # 循环 n 次
    for i in range(n):  # +1
        print(0)        # +1

但是2.3.3计算完整统计这里面没把循环本身算一次操作,只算了print

def algorithm(n: int):
    a = 1      # +0（技巧 1）
    a = a + n  # +0（技巧 1）
    # +n（技巧 2）
    for i in range(5 * n + 1):
        print(0)
    # +n*n（技巧 3）
    for i in range(2 * n):
        for j in range(n + 1):
            print(0)

[zwdzzs1]

不过影响不大🥰

[Alaso1]

虽然影响不大，但还是想请问一下，循环本身算是一次操作吗？

[duolingo1299]

好问题，我个人倾向于循环不算是一种操作，因为循环能做的事，不用循环也能做，只是可能会非常麻烦，所有我认为循环是操作的集合

…

---Original--- From: ***@***.***> Date: Sun, Nov 2, 2025 11:28 AM To: ***@***.***>; Cc: ***@***.******@***.***>; Subject: Re: [krahets/hello-algo]chapter_computational_complexity/time_complexity/ (Discussion #18) 虽然影响不大，但还是想请问一下，循环本身算是一次操作吗？ — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***>

[22097212d]

应该不算，但是每次循环条件判断应该算一次，或许可以理解为循环本身 获取Outlook for Android<https://aka.ms/AAb9ysg>

…

________________________________ From: Alaso1 ***@***.***> Sent: Sunday, November 2, 2025 11:28:38 AM To: krahets/hello-algo ***@***.***> Cc: REN, Chenguang [Student] ***@***.***>; Comment ***@***.***> Subject: Re: [krahets/hello-algo] chapter_computational_complexity/time_complexity/ (Discussion #18) CAUTION: This email is not originated from PolyU. Do not click links or open attachments unless you recognize the sender and know the content is safe. 虽然影响不大，但还是想请问一下，循环本身算是一次操作吗？ ― Reply to this email directly, view it on GitHub<#18 (reply in thread)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/BA23SQDW3IKD3UQZEYO3SRT32V26NAVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTIOBUHEYDKMA>. You are receiving this because you commented.Message ID: ***@***.***> [https://www.polyu.edu.hk/emaildisclaimer/PolyU_Email_Signature-v2.jpg] Disclaimer: This message (including any attachments) contains confidential information intended for a specific individual and purpose. If you are not the intended recipient, you should delete this message and notify the sender and The Hong Kong Polytechnic University (the University) immediately. Any disclosure, copying, or distribution of this message, or the taking of any action based on it, is strictly prohibited and may be unlawful. The University specifically denies any responsibility for the accuracy or quality of information obtained through University E-mail Facilities. Any views and opinions expressed are only those of the author(s) and do not necessarily represent those of the University and the University accepts no liability whatsoever for any losses or damages incurred or caused to any party as a result of the use of such information.

[Quantumin]

您好！在指数阶这一节里面的示例代码：
1 def exp_recur(n) -> int:
2 """指数阶（递归实现）"""
3 if n == 1:
4 return 1
5 return exp_recur(n - 1) + exp_recur(n - 1) + 1
6
7 """Driver Code"""
8 if name == "main":
9 n = 7
10 print("输入数据大小 n =", n)
11
12 count = exp_recur(n)
13 print("指数阶（递归实现）的操作数量 =", count)
这里面的count只是作为函数的返回值，并不适合用来表示操作数量吧？

[zhengads]

好难好难，暂时理解不了，不过继续往后推进，到时候有问题再回过头来看看，加油！！！

[krahets]

加油～

[butian1113]

我这个老年人，也有很多地方理解不了，特别是在递归中，总是想不清楚中间步骤。

[Sword-Holder-L]

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

[duolingo1299]

不会python呀

…

---Original--- From: ***@***.***&gt; Date: Fri, Nov 14, 2025 01:02 AM To: ***@***.***&gt;; Cc: ***@***.******@***.***&gt;; Subject: Re: [krahets/hello-algo]chapter_computational_complexity/time_complexity/ (Discussion #18) 您好！在指数阶这一节里面的示例代码： 1 def exp_recur(n) -&gt; int: 2 """指数阶（递归实现）""" 3 if n == 1: 4 return 1 5 return exp_recur(n - 1) + exp_recur(n - 1) + 1 6 7 """Driver Code""" 8 if name == "main": 9 n = 7 10 print("输入数据大小 n =", n) 11 12 count = exp_recur(n) 13 print("指数阶（递归实现）的操作数量 =", count) 这里面的count只是作为函数的返回值，并不适合用来表示操作数量吧？ — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***&gt;

[chaipuqia]

算法
算法无处不在，在我们生活中有广泛应用，算法就是有限步骤时间内解决问题的方法
复杂度分时间和空间两个层次，是计算评估算法效率的标尺
迭代式算法中的常见形式，最常用的有两种，for和while

for迭代 多用于在已知步骤数的程序下
/* for 循环 */实现求和，求1至i的所有数的总和
int forLoop(int n) { //定义一个函数，函数名叫forLoop，第一个int是传进去的变量类型，括号里的则是要传进去什么
int res = 0; //存放结果
// 循环求和 1, 2, ..., n-1, n
for (int i = 1; i <= n; ++i) {//int i=1 定义i； i<=n 假如i小于等于n就执行； 把i的值加一，递加运算符
res += i;//将值加入总和
}
return res;
}
while迭代 自由度要比for高很多，因为他实现循环都写在while里面，可叠加性高，就比如不仅要递加，还要乘2，他就方便许多
/while循环/实现功能同for
int whileLoop（int n）{
int res=0,i=1；
while（i<=n）{
res+=i;
++i;
}
return res;//标注参上
注意 for和while的本质逻辑是一样的，只是for更紧凑，while更灵活而已

下来学习建立在他们两个基础上的嵌套循环，顾名思义，就是一个循环套着一个循环
/下面我们以一个for循环套着一个while循环为例进行演示，打印一个直角三角形/
void twoLoop(int h){//假如不用返回变量就用void
for（int i=1； i<=h; ++i）{//重复执行h次,也就是输出h行，对i进行增加,在投放回去，让i1符合条件
int i1=1;
while（i1<=i）{
cout<<"*";//打印星号
++i1;//把它增加这样i1就不符合条件，返回上级
}
cout<<endl;//换行
}
}
我们来学习一下更深入的算法结构，是迭代的逆向思维（递归），他通过把任务分解成小任务（递），到达终止条件以后再往回倒（归）
/我么现在用递归来实现我们用迭代实现的功能/
int digui(int n){
if （n==1）{//到达最后一层是未执行rest变量的（因为还未定义，就开始反推了，他没有用），所以就可以顺利反推
return 1;//return 1就是开始反推，用n+res往回退。
}
int res = digui(n - 1);//调用自己，每次调用自己都会建一个递归层，每个递归层里都有自己的n和res，res值未定义，n用于运算（当前层），res用于接收。
return n+res;//把这一层的数据打包，放在上一层的res里，将子问题的解 res 与当前值 n 合并
//传送途径：函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。担忧可能会空间不够，溢出。
}
/递归优化版，尾递归，在递完成所有运算/
int digui2(int n1,int res1=0){
if （n1==0）{
return res1;
}
return digui2(n1 - 1,res1+n1);//在调用时，就把结果带下去，最后一键返回

}
下面我们再简单讲一下复杂度的评判标准，空间复杂度，和时间复杂度：
时间复杂度就是指算法运行所需步骤的趋势（就是随传入数据，步骤增加的速度，就比如每次加入变量，或把数值增大），分几种增加情况（字母O表示时间复杂度）
1.常数型：就是所需步骤不随传输的值变化而变化，一直都是一个固定的值，复杂度为O（1）。注意下面实例只为表现常数型，无实际意义。
/常数型代码/
int changshu（int n）{
int res=0 ，i=n
for（i； i<=n+1000； ++i；）{//不管n怎么变，都只计算n到n+1000所有数的和，进行1001次加法。
res+=i ；//进行累加
}
return res；
}
2.线型：所需步骤跟所传数据息息相关呈线性增长，复杂度为O（n）,能及时传进去的那个变量。
/线型代码/
int xian（int n）{
int res=0，i=0；
while（i<=n）{//循环次数随n进行变化
res+=i//进行累加
++i//实现循环
}
return res//注意假如定义函数时以int开头，要返还变量喔
}
3.平方型：时间复杂度是O（nn），多用于嵌套循环，就相当于两个线型复杂度的循环套在一起。代码我们这里给打印正方形。
/平方型代码，打印一个nn的正方形/
void dayin(int n){
for(int i=0; i<n; ++i){//一共有六行，重复执行n次
for(int a=0; a<n; ++a){//一共有n列，nn=n^2，
cout<<"";//输出星号
}
cout<<endl;//换行，不能放在第一个循环下面，因为第一行不用换行
}
}
4.指数型，就像细胞分裂一样，1生2，2生4，4生8……，他的时间复杂度极高，多见于2分递归树，复杂度为O（2^n）
/指数型代码，斐波那契数列/
int feibu(int n){
if (n==1|| n==2）{//斐波那契数列的第一个数和第二个数都是1
return 1;
}
int res=feibu(n-1)+feibu(n-2);//不断进行2分。对他们进行加法，直至回到n的原点（返回过程中）
return res;//到最后是返回上一级
}

阅读笔记，大家给我就纠错，补充补充

[chaipuqia]

参考一下其中的代码解释，尤其是递归部分，对理解很有帮助

[chaipuqia]

不过更重要的是谢谢k神

[LiLi-0226]

2.3 LiLi打卡

[mctheend]

上面系数可以忽略，是不是可以理解为当n趋向于无穷大时，2n2+7n+3与n2+n的比值即c是一个定值？

[fuzhao951]

大佬，打乱一个数组那里好像有点问题， Fisher-Yates 算法应该是倒着循环
for (let i = 0; i < n; i++) {
const r = Math.floor(Math.random() * (i + 1));
const temp = nums[i];
nums[i] = nums[r];
nums[r] = temp;
}

[CN-AL]

阶乘阶在数学上能理解，不知为何写成代码感觉有点乱，是递归不熟悉吗

[IDKW-xx]

你可以代一个数进去，n=10，for 产生 10 次计算并继续进行 n=9，for产生9次计算，以此类推就是n的阶乘

[Daniel-Zun]

精确渐进复杂度，念“Theta”