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

[zjj8421]

发自 Zhang JunJun 我目前使用NVDA这款开元屏幕阅读器来阅读浏览器中的网页内容，当然我猜Mac的旁白和Windows的讲述人表现和NVDA也差不多，我有一个非常简单的解决方案，当然不一定能快速应用到项目中。可以在网页渲染的时候，使用aria这种html属性标注公式块，将公式的父元素的aria-label设置为ascii math文本，这样我就可以读到公式的每一个字符，例如n的平方就是n^2，希望能采纳。至于PDF如何解决这个问题，目前还没想到方法。感谢！在 2024年5月5日，11:05，Ocean ***@***.***> 写道： 我猜测你可能看到的是 https://www.hello-algo.com/chapter_computational_complexity/time_complexity/#1 这一节的内容，我用 edge 自带的「大声朗读」测试了下，这种基于 mathjax 的行内公式是可以被阅读的，但行间公式也就是公式块的确无法阅读，稍微查了下 mathjax 上的无障碍支持，似乎开启了也只支持英文、西班牙语等，并不支持中文。 把相关的配置放在这里，期待开发者有更好的解决方案：https://www.osgeo.cn/mathjax/basic/a11y-extensions.html#a11y-extensions。 —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>

[zjj8421]

我目前使用NVDA这款开元屏幕阅读器来阅读浏览器中的网页内容，当然我猜Mac的旁白和Windows的讲述人表现和NVDA也差不多，我有一个非常简单的解决方案，当然不一定能快速应用到项目中。

可以在网页渲染的时候，使用aria这种html属性标注公式块，将公式的父元素的aria-label设置为ascii math文本，这样我就可以读到公式的每一个字符，例如n的平方就是n^2，希望能采纳。

至于PDF如何解决这个问题，目前还没想到方法。

感谢！

[ferryboy001]

我使用 NVDA + Access8Math 插件，某些情况下的确会出现不朗读，暂时没找到原因，但目前来说朗读是正常的。

[krahets]

某些情况下的确会出现不朗读，暂时没找到原因

@ferryboy001 有可能是 MathJax 未正常加载导致的，我前段时间修复了这个问题，现在加载应该比较 robust 了

[qiany-sui]

麻了对数概念全忘光, 对数相关内容看得云里雾里的, 真就是知识重新丢回给了老师

[S-Yuan137]

看到有位视障程序员和我们一起学习，很感动！希望我们的社区越来越有爱。也希望作者能看到这位程序员的需求。同时想，有没有利用AI来做无障碍阅读的产品？尤其是可以处理富文本图片等等的。希望能帮到他。

[krahets]

一方面，本书尽量保证屏幕阅读器可以顺利阅读所有文字和代码内容。另一方面，将图片用 AI 转化为语言描述可能是一个有效途径，但目前还没有可用的模型，我会持续关注

[zjj8421]

不用那么麻烦，写程序是很严谨的事情，ai搞出来的不一定就一定好理解，吧文中的公式能让读屏软件读成ascii math就可以，至于文章中的图片，主要的作用是帮助理解文本教程，而不是替代，所以不读也没什么的。

[ferryboy001]

使用 aria-label 的确可以无视各种环境限制，将源码作为图片的 alt 显示，但这种方式并不是可访问性最佳的方法，阅读效率上会非常低。

[krahets]

我不知道我的理解是否正确：加 aria-label 后，公式会以 LaTex 源码的形式被朗读，包括 \ , {} 等应被 MathJax 转义的符号？

[ferryboy001]

没错，这样的话的确可以通过读源码来理解，但失去了语义，读一些结构复杂的公式的体验是很糟糕的。

[ferryboy001]

其实还有一种便于使用纯文字阅读的格式，就是 AsciiMath，地位相当于 LaTeX 源码，将它用于图片的 alt 应该是可以的，但由于是纯文字，体验依然不如渲染后的体验好。如果找不到将 MathML 应用于 PDF 的方法，暂时用作 PDF 公式的阅读方案也是可以的。

[zjj8421]

ascii没问题。不知道所用的库有没有转换到ascii math的方法。

[ferryboy001]

对于一般的图表，例如文中的其他图片，使用 alt 是没有问题的，这样这些描述文字就不会被其他不使用屏幕阅读器的读者看到

[zjj8421]

能转换成ascii公式吗？我觉得阅读ascii公式是很无障碍的方式，ascii公式中没有代码。

[ferryboy001]

依然不如 access8Math，一旦结构复杂，就不能结构化的查看，本质上使用 asciiMath 也是线性的。

[zjj8421]

是的，但结构化的标签可能存在无障碍适配问题，比如读屏不能充分朗读这种标签，而ascii的问题是长公式较难理解，但ascii就在那，不好理解就多花一点时间，读屏能获得的信息是完整的。

[zjj8421]

感谢大家对无障碍问题的关注，现在我学到树结构了，我遇到时间复杂度、空间复杂度的公式的时候，就只能靠猜，还好的是，了解了基本概念自己是能算出来的，但如果能读到公式，就能确认自己想的是否正确，学的会更自信一些。

[yin-b]

很棒

[Icemanzzt]

k神，2.3.2中，【我们将线性阶的时间复杂度记为O(n)】,这里会不会产生一个歧义，非线性阶时间复杂度不是大O表示法呢？

[freesky3]

应该往后面内容看了就不会把

[freesky3]

我在想渐进上界的定义是不是不充分（虽然我查到的定义也是这样）。按这个定义，本来为O(n)复杂度的程序，也可以说e^n是渐进上界，但这并没有体现“渐进”和增长趋势相同。我粗略想了一个可能的定义：在在原来的基础上，加上存在c2>0，使c2 * f(n) <= T(n) <= c * f(n)。

[krahets]

很好的问题，从数学上看，$e^n$ 和 $n$ 都可以看作 $T(n) = 2n + 1$ 的渐近上界。但从复杂度分析的角度看， $e^n$ 作为渐近上界无法给出有用信息，我们希望渐近上界尽可能“紧密”地描述 $T(n)$ 的增长趋势。

[Everythingismetaphor]

细胞分裂的count是什么意思，模拟细胞分裂为什么还有加上分裂之前的，细胞分裂之后原来的细胞就没了

[Dog00]

模拟的是细胞的分裂次数，也是递归树的节点数

[brian4159]

for _ in 0..n {
    base *= 2;
    count += base;
    print!("count的值是{} ", count)
 }

细胞分裂，这样循环不就可以了吗 为什么要套一层base循环呢

[dukue]

不错的问题，我的理解是
第一个循环：for _ in range(n):这个循环控制细胞分裂的轮数，即 n 轮。
第二个循环：for _ in range(base): 这个循环在每一轮分裂中，模拟细胞的分裂过程。base 表示当前轮次前的细胞数量，因此这个循环会执行 base 次，每次增加一个细胞到 count。
至于你给出的代码我觉得也没有问题，每次分裂翻倍后加到总数上，但是这个例子是在讨论细胞分裂的问题不是嘛，所以第二个 for 循环确保每个细胞在每一轮分裂中都被考虑，模拟了细胞分裂成两个的过程。

[xlyyddy]

作者给出的例子是拿来说指数阶时间复杂度的，是用细胞分裂来模拟·时间复杂度达到指数阶，相当于每个细胞分裂一次就是一次循环，最终时间复杂度计算为O（2^n）,你这个虽然也是细胞分裂，但是时间复杂度更低，不能拿来解释指数阶的时间复杂度

[921000]

阶乘的计算 是不是不太对啊？时间复杂度应该是 O(n)
int factorialRecur(int n) {
if (n == 1)
return 1;
return n * factorialRecur(n - 1);
}

[whale-G]

书中实现计算阶乘的代码没有问题，是不同的实现方式。

/* 阶乘（递归实现） */
int factorialRecur(int n) {
    if (n == 0)
        return 1;
    // 每次在计算n！时，需要计算(n-1)!
    int count = 0;
    for (int i = 0; i < n; i++) {
        count += factorialRecur(n - 1);
    }
    return count;
}

书中的实现方式会进行大量的重复计算，比如n==5时，进行5次循环，每次循环计算n==4的情况，n==4时再进行4次循环，每次循环计算n==3的情况。依次类推，在到达终止条件n==0时，依次返回1*1、2*1、3*2、4*6、5*24得到最终结果存储在count。
这种实现方式会重复多次计算相同的情况，所以时间复杂度高，算法实现的不好。作者应是为了举例复杂度O(n!)的例子。

---

你的算法是常见的阶乘实现方式，时间复杂度是O(n)没错。不过没有考虑0!的情况。

[chaorendijia666]

关于2.3.2和2.3.3处，
为什么
【for i in range(5 * n + 1):
print(0)
】
的操作数量是(5n+1)；
而
【
for i in range(n): # +1
print(0) # +1
】
的操作数量是2n?

[siqingbushou]

因为前者用了技巧2省略所有系数

[chaorendijia666]

谢谢，因为作者在2.3.3处写的是完整版公式和简化版公式的对比，所以我理解完整版公式应该是完整的

[yalezhangk]

请教一下，那我们通常所说的时间复杂度O()，是指最坏时间复杂度还是平均时间复杂度啊?

[lei-ctyh]

最坏时间复杂度

[Jeffstarm]

指数阶的例子中，exp_recur(n - 1) + exp_recur(n - 1)+1为什么不写成2exp_recur(n - 1)+1呢，二者有区别吗

[vincentwusining]

因为那样就不是分裂了，时间复杂度变成O(n)了。分开来写虽然是一样的代码，但是运行两遍。合起来写，2只是运行一遍，把结果2，没有运行2遍。