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

[wuxianggujun]

函数渐近上界开始我就看不懂了，giao，废了

[1435646097]

大概就是X越来越大后，Y的趋势

[zhanglei1032]

看不懂就先记住几个常见的，慢慢就懂了

[deyu9999]

平均复杂度那个符号怎么读？

[1435646097]

我也想知道

[zhanglei1032]

就是数学符号的Theta，中文读音接近C塔

[LCCVitno]

线性对数阶那个层数没有+1吧

[tyhzxh]

写的太好了

[daiDai-study]

打卡

[fanhefeng]

大佬好。冒泡排序代码中有行注释“元素交换包含 3 个单元操作”。我的问题是，javascript es6有个解构语法可用作交元素交换，若此种写法，是否依然需要3个单元操作？

    [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]

[krahets]

这种情况下，系统会为右侧的表达式 [nums[j + 1], nums[j]] 创建一个包含两个元素的临时数组，因此仍然可以理解为需要 3 个（左右）的单元操作

[zerosea330]

log n 递归树那里，返回参数为 n/2，是不是会出现浮点数的情况。

[krahets]

是哪个语言呢？在大多数语言中，n / 2 是整除

[zhanglei1032]

Python就不是整除，可以把例子里面的n=8换成n=9试试，不过不影响复杂度的结论

[Ycloud2024]

图2-7和2.3.2函数渐进上界写的不太严谨。首先，2.3.2里int a = 1算操作数+1，但是int i = 0没算。其次，i < n判断操作没算。最后，T(n)应该是等于5+3n，多了int i = 0（操作+1）和判断操作i < n（操作+n+1）。图2-7的算法运行时间只考虑了打印时间，怎么看都和下面2.3.2的内容不搭。

[krahets]

你很细心！我们本可以展开一段讲 for 循环的单元操作数量包含哪些，为什么这里是 + 1 、那里是 + 3 等等。但我没有选择这样做，因为认为这对初学者来说必要性不大，并且不同编程语言的“读感”也是不一样的：

2.3.2里int a = 1算操作数+1，但是int i = 0没算。其次，i < n判断操作没算

我们把每轮 for 循环简化看作 1 次单元操作，主要是因为：在一些语言中（例如 Python、Swift、Rust 等），我们不容易看出每次 for 循环包含几个单元操作，从直接的语义上看就是 1 个。

图2-7的算法运行时间只考虑了打印时间

把 for 循环的操作进行统计进去也是可以的，但不会对我们的分析过程产生任何影响（我们的本意就是拿打印操作举例，而不是循环操作），因此我认为这里的简化是可取的

[jiuerya7]

把for循环简化看作1次单元操作，为什么2.3.2求操作量还要统计i++的次数，得到结果是3+2n，而不是3+n，到2.3.3又突然不统计i++和j++，只统计了循环内部的操作，我看了这个评论才反应过来

[krahets]

@jiuerya7 这里的 2n 分别是 for 循环和打印操作，我们是把“for”这一行记为一个单元操作。这一点上本文 2.3.1, 2.3.2, 2.3.3 是统一的。

[T00ler]

随机打乱为啥只能选i之前的数进行替换，第二行为啥不用const r = Math.floor(Math.random() * n);
// 随机打乱数组元素
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;
}

[NgxuAnGMH]

最重要是记住时间复杂度那幅图：
1、$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$
2、记住 log(n) 是步长对半缩减，2^n 是步长翻倍增加。（条件变量）

• 另外注意，递归函数是如何拆解问题的

[zjj8421]

我是一位视障程序员，我在网上找了很多数据结构和算法的资料，很多都用图片展示代码片段，后来发现Hello算法非常1接地气，也很无障碍，阅读了几节之后，遇到一个问题，希望作者能考虑修改一下。我在使用PDF和在线版本的时候

[zjj8421]

比如本章中有一句是这样的：“假设输入数据大小为

”，这个数据大小后面的字符我用屏幕阅读器是无法朗读出来的，我猜测使用了一些非常规字符，建议替换为常用的字符，有任何困惑可以发邮件zhang-junjun@foxmail.com与我交流，感谢作者的Hello算法项目。

[ocean0117]

我猜测你可能看到的是 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。

[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如何解决这个问题，目前还没想到方法。

感谢！

[qiany-sui]

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

[S-Yuan137]

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