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

[OU-y-x]

请问第5点对数阶那里的图片（图2-12），虽然有logn+1层，但计算操作总数不应该是logn次吗？n=1时，不会执行while循环。有人可以解释一下吗？万分感谢！！！

[wu-diu-diu]

是的,while循环只会执行logn次，复杂度是logn

[OU-y-x]

你说的是return count；吗？可是当数组长度为1时（也就是n=1时），确实没有计算操作诶

[hjzzjh]

同样的疑问，计算次数应该是logn，n=1时，不会执行n=n/2操作。

[WangShuToMoon]

请教一个问题: 为什么作者给出的两个函数第一个算上for循环那一步，第二个不算for循环那一步？

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
这个作者加上了for循环的那一步，T(n)=3+2n，但是AI 给出的结果是T(n)=3+n，没有加上for循环的那一步;

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)
这个作者没加上for循环的那一步，结果是T(n)=2+(5n+1)+2n(n+1)=2n**2+7n+3，而AI 给出的结果是一样的

[Liucc-123]

可以以AI的为准，计算操作执行次数，不需要包含循环本身

[jiuerya7]

因为n的系数跟渐进上界f（n）的值没有关系，所以i++那一步的操作数可以忽略

[jiuerya7]

所以3+n就可以，作者的3+2n是还没有讲到渐进函数f（n）

[hjzzjh]

二叉树的高度：从跟节点到最远叶节点所经过的“边”的数量。而非节点的数量。

[Ganzhongxue]

初学者想请教个问题：
// 在某运行平台下
void algorithm(int n) {
int a = 2; // 1 ns
a = a + 1; // 1 ns
a = a * 2; // 10 ns
// 循环 n 次
for (int i = 0; i < n; i++) { // 1 ns
cout << 0 << endl; // 5 ns
}
}
这段代码书上给的是6n+12 ，我觉得for循环在i = n的时候还会判断一次所以是6n+13，我去问kimi他又和我说是下面这样，所以到底是多少呢？以下是kimi说的

我们可以按照以下步骤计算运行时间：
初始化变量：
int a = 2; 需要 1 ns
a = a + 1; 需要 1 ns
a = a * 2; 需要 10 ns
循环操作：
循环 n 次，每次循环包括：
int i = 0; 需要 1 ns（仅在循环开始时执行一次）
i < n; 需要 1 ns（每次循环执行一次）
i++ 需要 1 ns（每次循环执行一次）
cout << 0 << endl; 需要 5 ns（每次循环执行一次）
循环总时间：
循环开始时的初始化 int i = 0; 需要 1 ns
循环条件 i < n; 和循环变量递增 i++ 各需要 1 ns，共 2 ns，循环 n 次，总时间 2n ns
打印操作 cout << 0 << endl; 需要 5 ns，循环 n 次，总时间 5n ns
总运行时间：
初始化变量总时间：1 + 1 + 10 = 12 ns
循环总时间：1 + 2n + 5n = 1 + 7n ns
因此，算法的总运行时间为：
12+1+7n=7n+13 ns

[nshizhongfeng]

i++的时候才会记一次, 也就是说相当于(0, n]左开右闭的区间, 次数的话就是n

[SuperZhangRui]

继续学习继续加油！！！

[hanzhe-one]

😶‍🌫️

[hanzhe-one]

okkk

[YissWho]

day2

[Lpf-357]

2025.3.11

[HBB0517]

打卡
319

[GodGoldenCake]

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

[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]

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

[xvwenya]

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

[xvwenya]

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

[Joanna-0427]

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

[Ivy129]

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

[Ivy129]

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

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

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

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