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

[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遍。

[majiang213]

代码需要可以运行

[hopeyl]

在计算运行时间和操作数时，没有包括循环变量初始化的操作，以及每次循环条件比较的操作？

[John12345656]

我觉的，他这些初始化、比较的操作相较于后面的具体功能（具体功能可能是一个长耗时的操作）耗费的时间较少可以忽略不计。

[hopeyl]

在前面计算具体用时示例还有计算操作数量的示例中，赋值语句都算1ns，循环变量初始化（也是赋值）也应该算1ns，比较操作也应该类似吧

[yiyi-2020]

hh 百度搜 “像耳机一样的符号” 欧米茄（Ω）

[Mighty-Frog]

时间复杂度的数学定义有点问题，这个定义给出的是个上界，但不是紧致上界，依定义线性复杂度算法既是O(n), 也是O(n2)，还是O(nn)。应该给出的是一个被常数夹逼的区间：如果存在常数 c_1 、 c_2 和 n_0 ，使得对于所有 n > n_0 ，都有： c_1 * f(n) < T(n) < c_2 * f(n) ，我们说 T(n) 是 O(f(n)) 。

[DengDengDengF]

我想博主意思，如果上下界都知道，的确可以更好的去描述f(n)。但是，实际情况对于比较复杂的算法，只能证明f(n)的上界，也就是最坏时间复杂度.

[zyh778]

在指数阶运算的第三段代码中，return exp_recur(n - 1) + exp_recur(n - 1) + 1这里为什么加了两次exp_recur(n - 1)啊

[TianMaker]

一分为二，然后加一是算上分裂之前的一个

[DengDengDengF]

经过n次分裂后 2^0 +2^1 +2^n =2^n -1 T（n） =2^n - 1 用类比法，如下 T(1)=1 T(2)=2^2 - 1 =3 T(3)=2^3 - 1 =7 …… 代码里 expRecur（n）=expRecur(n - 1) + expRecur(n - 1) + 1 expRecur（n）=2 * expRecur(n - 1) + 1 expRecur(1)=1 expRecur(2)=2 * expRecur(1) + 1=3 expRecur(3)=2 * expRecur(2) + 1 =7 ……. 所以 expRecur（n）=T（n）=2^n - 1 代码可以去计算，经过n次分裂后的数据 就是用简单数学换算。 null yimu ***@***.***>于2024年10月16日 周三23:05写道：

…

在指数阶运算的第三段代码中，return exp_recur(n - 1) + exp_recur(n - 1) + 1这里为什么加了两次exp_recur(n - 1)啊 — Reply to this email directly, view it on GitHub <#18 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AVZFKIP35JTJTMOULQKSF2TZ3Z6DTAVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAOJWGEZDENA> . You are receiving this because you commented.Message ID: ***@***.***>

[zyh778]

嗷嗷，这样啊，明白了，谢谢

[DengDengDengF]

好迷茫啊 以后全栈还是大前端 null yimu ***@***.***>于2024年10月17日 周四19:57写道：

…

嗷嗷，这样啊，明白了，谢谢 — Reply to this email directly, view it on GitHub <#18 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AVZFKIMG2EQE7GNYWCMXPRLZ36Q3LAVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAOJXGA3TCNA> . You are receiving this because you commented.Message ID: ***@***.***>

[beihuxiansheng]

全栈已经提了快10年了，谁听谁惨，不要走技术方面的全栈

[DengDengDengF]

兄弟 指点一下 null beihuxiansheng ***@***.***>于2024年10月24日 周四15:19写道：

…

全栈已经提了快10年了，谁听谁惨，不要走技术方面的全栈 — Reply to this email directly, view it on GitHub <#18 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AVZFKIJDQC2PIB5XBO6ZAVLZ5CNOZAVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCMBTG4ZTMOI> . You are receiving this because you commented.Message ID: ***@***.***>

[blossom-breeze]

由于输入数组是被打乱的，因此元素 1
出现在任意索引的概率都是相等的，那么算法的平均循环次数就是数组长度的一半 2/n，各位大佬们指点一下，最后这个2/n，没看懂，晕，感恩

[fakerUNcode]

因为出现在任何位置的可能性都一样，可能的有位置设为i(1≤i≤n),位置在i处就要遍历i-1次（例如在第一个就完全不需要遍历就是0），所以可能遍历的次数有：0,1,2,3......n，然后求这个数列的平均值就得到了，不懂的话画个图：）

[the-glory-days]

在指数阶运算的第三段代码中，return exp_recur(n - 1) + exp_recur(n - 1) + 1这里为什么要加1啊

[DengDengDengF]

就是等比数列求和的变形 s（n）= 2^n - 1 s（n）= 2 * s（n-1） + 1 同理，你也可以整出其他花样 null LI Jiaxing ***@***.***>于2024年11月15日 周五20:36写道：

…

在指数阶运算的第三段代码中，return exp_recur(n - 1) + exp_recur(n - 1) + 1这里为什么要加1啊 — Reply to this email directly, view it on GitHub <#18 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AVZFKIJBNOLPZ6HEEW7SO6D2AXTD3AVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCMRWGY2TCNQ> . You are receiving this because you commented.Message ID: ***@***.***>