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

[YissWho]

day2

[Lpf-357]

2025.3.11

[HBB0517]

打卡
319

[YAN-CodeSpring]

如果有人回复我消息，我该在哪里看到消息提醒？还是说我要回到这个章节翻我之前的评论我才能看见吗？感谢解答！

[iwtbf]

回你一下你试一试

[YAN-CodeSpring]

谢谢你，我在github和qq邮箱都收到了消息提醒！

[Kruogu]

你只收到一条信息吗？这个楼下面所有人发出的信息我都可以收到

[WeChatWeGPT]

/* 阶乘阶（递归实现） */
int factorialRecur(int n) {
if (n == 0)
return 1;
int count = 0;
for (int i = 0; i < n; i++) {
count += factorialRecur(n - 1);
}
return count;
}
这个不是阶乘，作者大大

[KeXu1739]

他说的是 阶乘 阶， 没说是阶乘

[jiyunpeng910925]

这应该是代码执行的次数（时间复杂度），最终是一个阶乘的结果

[Potato-2020]

是的，主要疑惑，为什么要用循环呢，其实循环代码，翻译过来，就是nfactorialRecur(n-1)
每次递归调用 factorialRecur(n - 1) 实际上计算的是 (n−1)!
循环执行 n次，因此结果是 n(n-1)!
他可能是怕别人看不懂，所以...？但是，效果不太好，让更多的小白看不懂了啊。既然函数名称是阶乘递归，我觉得还是写大众共识代码吧（西红柿炒鸡蛋，放辣椒不好吃！！！），毕竟，递归的目的就是：思路直观
int factorialRecur(int n) {
if (n == 0) return 1;
return n * factorialRecur(n-1);
}
另外呢？我看到有人回复：这是阶乘阶，没说阶乘。。。希望别被带跑偏了，阶乘“阶”，也可以叫做阶乘"级"，这里只是形容词，仅此而已，用来形容时间复杂度的级别、阶层....等等形容词吧，理解就好

[Potato-2020]

哦，对了，想到了一个，他写for循环的理由，JVM虚拟机上，加法运算，比乘法运算，速度更块，因为策划给你发运算，要开辟更多的栈空间，用于储存临时变量。
用加法代替乘法。实在想不出别的理由了

[xvwenya]

“时间复杂度能够有效评估算法效率。例如，算法 B 的运行时间呈线性增长，在 n>1时比算法 A 更慢，在
n>1000000时比算法 C 更慢。事实上，只要输入数据大小 n足够大，复杂度为“常数阶”的算法一定优于“线性阶”的算法，这正是时间增长趋势的含义。”中的
“在 n>1时比算法 A 更慢”是不是有些不恰当，
根据图上的增长趋势来看的话，不应该是n>1时算法A 的运行时间增长趋势才更慢，n<=1时，B和A的趋势相近（或者说这时B的时间更加接近于A），因为A是常数阶不是吗

[xvwenya]

我的问题，这里应该是说的算法的效率，而不是算法的时间复杂度

[zengfantaoGit]

其实就是算操作时间，因为 n > 1 时 B算法肯定需要大于1的操作时间，而A算法恒定1的操作时间。所以才判定 A算法优于 B算法

[Joanna-0427]

真诚提问，想请问下大家这本书看了适合新人吗，怎么样。我看了两天感觉很多概念很晦涩，递归，分治，各种排序。我是一个转码纯小白，刚学完python，不知道是不是有适合新人的数据结构与算法推荐。谢谢！

[Ivy129]

多看多练，概念多咀嚼，慢慢就会了，不用急

[Ivy129]

打卡 2025.6.9
1.算法复杂度计算
第一步，统计操作数量；第二步，判断渐进上界

2.常见类型的时间复杂度
比较好搞定的是相加，常数这些，嵌套是相乘，因为比较好理解，而且比较常见，但是比较需要额外了解一下的是指数阶，对数阶和阶乘阶，这个在之前没有出现过。
在实际算法中，指数阶常出现于递归函数中。
指数阶增长非常迅速，在穷举法（暴力搜索、回溯等）中比较常见。对于数据规模较大的问题，指数阶是不可接受的，通常需要使用动态规划或贪心算法等来解决。

与指数阶相反，对数阶反映了“每轮缩减到一半”的情况。
对数阶常出现于基于分治策略的算法中，体现了“一分为多”和“化繁为简”的算法思想。它增长缓慢，是仅次于常数阶的理想的时间复杂度。

3.最佳、最差、平均时间复杂度
算法的时间效率往往不是固定的，而是与输入数据的分布有关。
总结：最差时间复杂度更为实用，因为它给出了一个效率安全值

[yanqingyang]

大佬，2n+10000*(n10000)的时间复杂度不应该是O(n10000)吗？为什么表中是O(2n)?

[yanqingyang]

2^n+10000*n^10000的时间复杂度不应该是O(n^10000)吗？为什么表中是O(2^n)?

[22097212d]

n^10000还是属于平方阶（n^m,m为常数，都属于平方价），当n足够大时，指数阶增长速率更大

[lhyjs]

因为 2^n 的 增长速率比 n^10000 快（指数爆炸，指数的形式增长速率非常快）

[Affirm-pm]

请问这里的代码报错怎么办，我是运行了iteration.cpp文件，然后报错如下：
[{
"resource": "/c:/CODE_filed/CODE_cpp/unit/hello/utils/tree_node.hpp",
"owner": "cpptools",
"severity": 4,
"message": "comparison of integer expressions of different signedness: 'int' and 'std::vector::size_type' {aka 'long long unsigned int'} [-Wsign-compare]",
"source": "gcc",
"startLineNumber": 44,
"startColumn": 20,
"endLineNumber": 44,
"endColumn": 20
},{
"resource": "/c:/CODE_filed/CODE_cpp/unit/hello/utils/tree_node.hpp",
"owner": "cpptools",
"severity": 4,
"message": "comparison of integer expressions of different signedness: 'int' and 'std::vector::size_type' {aka 'long long unsigned int'} [-Wsign-compare]",
"source": "gcc",
"startLineNumber": 62,
"startColumn": 14,
"endLineNumber": 62,
"endColumn": 14
}]

[Affirm-pm]

我是将github上的有代码的文件夹全部导入到我以前一直自己写的cpp文件（可以正常运行）的并列位置了，请问这样对吗？

[ZhaoBuyan]

不同符号的整数表达式比较：'int' 和 'std::vector::size_type'（即 'long long unsigned int'）

[1aa-1]

小学生第二天打卡，7.11

[Phi-BS]

我来稍微解释一下为什么“每轮缩减到原来的一半”意味着问题规模是对数阶。
def logarithmic(n: int) -> int:
"""对数阶（循环实现）"""
count = 0
while n > 1:
n /= 2
count += 1
return count
显然，n=1时循环终止。当然也可能有其它情况，比如n先是1.1、自除以2后变为0.55，以0.55退出循环。这里简化问题，认为n是以1退出循环的，在问题规模较大时由这种简化带来的误差可以忽略。

因为每次操作后、n都变为原来的一半，所以操作k次后n变为n / 2^k。
假设k次操作后，n以1退出循环，则
n / 2^k = 1
n = 2^k
从中即可解出k=log_{2} n，即操作次数是n的对数阶，就是这么来的。

[22097212d]

都能收到（悲） 获取Outlook for Android<https://aka.ms/AAb9ysg>

…

________________________________ From: Kruogu ***@***.***> Sent: Thursday, August 28, 2025 5:32:50 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/BA23SQA72IZONENES4OL66D3PYPYFAVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTIMRTG43TEMQ>. 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.

[YAN-CodeSpring]

我都能收到，不过可以退订，就不会有很多人打扰了

…

------------------&nbsp;原始邮件&nbsp;------------------ 发件人: "krahets/hello-algo" ***@***.***&gt;; 发送时间:&nbsp;2025年8月28日(星期四) 中午11:25 ***@***.***&gt;; ***@***.******@***.***&gt;; 主题:&nbsp;Re: [krahets/hello-algo] chapter_computational_complexity/time_complexity/ (Discussion #18) 都能收到（悲） 获取Outlook for Android<https://aka.ms/AAb9ysg&gt; ________________________________ From: Kruogu ***@***.***&gt; Sent: Thursday, August 28, 2025 5:32:50 AM To: krahets/hello-algo ***@***.***&gt; Cc: REN, Chenguang [Student] ***@***.***&gt;; Comment ***@***.***&gt; 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)&gt;, or unsubscribe<https://github.com/notifications/unsubscribe-auth/BA23SQA72IZONENES4OL66D3PYPYFAVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTIMRTG43TEMQ&gt;. You are receiving this because you commented.Message ID: ***@***.***&gt; [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. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***&gt;

[heavenly-zy]

从这章开始变得难啃了 o(╥﹏╥)o