chapter_computational_complexity/time_complexity/ #18
Replies: 171 comments 244 replies
-
Beta Was this translation helpful? Give feedback.
-
|
本页中n^2的讲解中,以「冒泡排序」为例,外层循环n-1 次,内层循环···次,平均为n/2次,因此时间复杂度为 ··· 。在这里计算的是最差时间复杂度,是不是描述应该为计算内层冒泡排序次数的等差数列求和,而不是平均n/2再乘以外层(n-1)的描述,感觉容易造成歧义。 |
Beta Was this translation helpful? Give feedback.
-
|
最差 O 平均 θ 最优 Ω |
Beta Was this translation helpful? Give feedback.
-
|
大佬好,界面是不是加一个“返回顶部”的按钮会更方便些呀; |
Beta Was this translation helpful? Give feedback.
-
|
大佬你好,我是一个算法小白,在看公式时就有了困难,比如这个公式T(n)= 3 +2n,文中也没有具体写是怎么推导出来的,不仅如此,其他公式的推导好像也没有太详细。不知我是不是还该继续看下去。 |
Beta Was this translation helpful? Give feedback.
-
指数阶, 那个代码里面应该是 return expRecur(n - 2) + expRecur(n - 1) + 1吧; |
Beta Was this translation helpful? Give feedback.
-
|
哈喽,k大,worst_best_time_complexity.cpp 代码编译时出错 ➜ 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));
| ^~~~~~~原因是在
添加后编译通过,运行正常 ➜ 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
|
Beta Was this translation helpful? Give feedback.
-
|
看不明白,这章好像只是知道了时间复杂度的表示方式。 |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
|
K神,阶乘阶的操作总数应该不是等于最底层结点数量吧,是所有结点中的操作总数之和吗? |
Beta Was this translation helpful? Give feedback.
-
|
指数阶这段没看懂count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1。为什么最后等于2^n - 1 |
Beta Was this translation helpful? Give feedback.
-
|
能看到这本书真的太好了 |
Beta Was this translation helpful? Give feedback.
-
|
我不太清楚是不是我的系统问题,这两天一直在看,前几天似乎没问题。今天起的教程似乎所有显示数学公式的地方都出了问题?比如2.2.4中的一段变成了这样: 以下示例展示了使用上述技巧前、后的统计结果。 Edge 和 Chrome 都有这样的显示问题 |
Beta Was this translation helpful? Give feedback.
-
|
学习数据结构画图太重要了,作者的图画的太棒啦,可以知道是什么软件画的吗 |
Beta Was this translation helpful? Give feedback.
-
/* 指数阶(递归实现) */
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,所以可以这样递归写。 看完gpt的答案我也懂了,感觉可以参考gpt的回答改进一下。 上述函数的时间复杂度为指数阶(Exponential Time),记作O(2^n)。 在函数中,每次递归调用expRecur(n - 1)会导致另外两次递归调用,因此函数的递归深度将以指数级增长。每次递归调用的时间复杂度是常数级的,但由于递归的次数是指数级的,因此整体时间复杂度也是指数级的。 简单来说,随着输入n的增加,函数的执行时间将指数增长,导致非常低效。因此,这是一个效率较低的实现,特别是在处理大型输入时。如果需要更高效的实现,可以考虑使用其他算法或优化技巧来减少递归的次数。 |
Beta Was this translation helpful? Give feedback.
-
|
常数阶的操作数量与输入数据大小无关,即不随着的变化而变化。 在以下函数中,尽管操作数量 size 可能很大,但由于其与输入数据大小无关,因此时间复杂度仍为 : 其实在一些例子的选取上就能看到作者真的蛮用心的~ 感谢 https://www.hello-algo.com/chapter_computational_complexity/time_complexity/#2 |
Beta Was this translation helpful? Give feedback.
-
|
可视化看不了 |
Beta Was this translation helpful? Give feedback.
-
|
有点小问题,2.3.2这里把循环本身也算一次操作 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但是2.3.3计算完整统计这里面没把循环本身算一次操作,只算了print 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) |
Beta Was this translation helpful? Give feedback.
-
|
好问题,我个人倾向于循环不算是一种操作,因为循环能做的事,不用循环也能做,只是可能会非常麻烦,所有我认为循环是操作的集合
…---Original---
From: ***@***.***>
Date: Sun, Nov 2, 2025 11:28 AM
To: ***@***.***>;
Cc: ***@***.******@***.***>;
Subject: Re: [krahets/hello-algo]chapter_computational_complexity/time_complexity/ (Discussion #18)
虽然影响不大,但还是想请问一下,循环本身算是一次操作吗?
—
Reply to this email directly, view it on GitHub, or unsubscribe.
You are receiving this because you commented.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
应该不算,但是每次循环条件判断应该算一次,或许可以理解为循环本身
获取Outlook for Android<https://aka.ms/AAb9ysg>
…________________________________
From: Alaso1 ***@***.***>
Sent: Sunday, November 2, 2025 11:28:38 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/BA23SQDW3IKD3UQZEYO3SRT32V26NAVCNFSM6AAAAAASLISNF6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTIOBUHEYDKMA>.
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.
|
Beta Was this translation helpful? Give feedback.
-
|
您好!在指数阶这一节里面的示例代码: |
Beta Was this translation helpful? Give feedback.
-
|
好难好难,暂时理解不了,不过继续往后推进,到时候有问题再回过头来看看,加油!!! |
Beta Was this translation helpful? Give feedback.
-
|
时间复杂度分析统计的不是算法运行时间,而是算法运行时间随着数据量变大时的增长趋势。 |
Beta Was this translation helpful? Give feedback.
-
|
不会python呀
…---Original---
From: ***@***.***>
Date: Fri, Nov 14, 2025 01:02 AM
To: ***@***.***>;
Cc: ***@***.******@***.***>;
Subject: Re: [krahets/hello-algo]chapter_computational_complexity/time_complexity/ (Discussion #18)
您好!在指数阶这一节里面的示例代码:
1 def exp_recur(n) -> int:
2 """指数阶(递归实现)"""
3 if n == 1:
4 return 1
5 return exp_recur(n - 1) + exp_recur(n - 1) + 1
6
7 """Driver Code"""
8 if name == "main":
9 n = 7
10 print("输入数据大小 n =", n)
11
12 count = exp_recur(n)
13 print("指数阶(递归实现)的操作数量 =", count)
这里面的count只是作为函数的返回值,并不适合用来表示操作数量吧?
—
Reply to this email directly, view it on GitHub, or unsubscribe.
You are receiving this because you commented.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
算法 for迭代 多用于在已知步骤数的程序下 下来学习建立在他们两个基础上的嵌套循环,顾名思义,就是一个循环套着一个循环 } 阅读笔记,大家给我就纠错,补充补充 |
Beta Was this translation helpful? Give feedback.
-
|
2.3 LiLi打卡 |
Beta Was this translation helpful? Give feedback.
-
|
上面系数可以忽略,是不是可以理解为当n趋向于无穷大时,2n2+7n+3与n2+n的比值即c是一个定值? |
Beta Was this translation helpful? Give feedback.
-
|
大佬,打乱一个数组那里好像有点问题, Fisher-Yates 算法应该是倒着循环 |
Beta Was this translation helpful? Give feedback.
-
|
阶乘阶在数学上能理解,不知为何写成代码感觉有点乱,是递归不熟悉吗 |
Beta Was this translation helpful? Give feedback.
-
|
精确渐进复杂度,念“Theta” |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
chapter_computational_complexity/time_complexity/
动画图解、一键运行的数据结构与算法教程
https://www.hello-algo.com/chapter_computational_complexity/time_complexity/
Beta Was this translation helpful? Give feedback.
All reactions