chapter_computational_complexity/space_complexity/ #19
Replies: 36 comments 44 replies
-
【Fig. 空间复杂度的常见类型】图片曲线画的不对,可以找找相关的函数图线工具,目前的曲线有一定的误导,比如如果知道数据量为n<8的情况下选择哪种时间复杂度更合适?按照图线会得出一个错误结论。 |
Beta Was this translation helpful? Give feedback.
-
在第一个示例的 func funcName() {} 方法是指: func (s *this) methodName() {} |
Beta Was this translation helpful? Give feedback.
-
有个疑问 /* 递归 O(n) */
void recur(int n) {
if (n == 1) return;
return recur(n - 1);
} 这段代码不是尾递归吗? |
Beta Was this translation helpful? Give feedback.
-
空间复杂度和时间复杂度内容比较像,所以这章细节不如上一章多。感谢K神 |
Beta Was this translation helpful? Give feedback.
-
打卡,二叉树的例子不是很懂,等学完再回来 |
Beta Was this translation helpful? Give feedback.
-
我的直觉告诉我递归遍历二叉树的空间复杂度应该是远小于O(2^(n - 1)),考虑递归调用过程,只有每进入树的下一层的时候,才会增加一个栈帧,而每当返回上一层的时候就会立即销毁一个栈帧,即是说栈帧数量与递归深度成正比,如果递归代码里没有只malloc()而不free()的行为,那空间复杂度应该是O(n)。用图解的方式说,从根节点画一条线到当前递归代码所在节点,只有在线上的节点才创建了栈帧,不在线上的节点要么栈帧已经无效,要么还没创建栈帧。 |
Beta Was this translation helpful? Give feedback.
-
def build_tree(n): |
Beta Was this translation helpful? Give feedback.
-
2.4.3这里讲了5种空间复杂度类型,图2-6列出了从低到高的次序,可是下面为什么没有按照这个次序,讲完了指数类型又讲到对数类型呢 |
Beta Was this translation helpful? Give feedback.
-
python二叉树报错的,可以尝试补一下TreeNode类的定义: # Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right |
Beta Was this translation helpful? Give feedback.
-
常见的几个类型的英文翻译(GPT4 生成):
|
Beta Was this translation helpful? Give feedback.
-
归并排序的空间复杂度为什么是O(logn)啊,不是每个节点递归都要分配栈帧,为什么等于树高 |
Beta Was this translation helpful? Give feedback.
-
发现右侧的目录,latex公式没有生效 |
Beta Was this translation helpful? Give feedback.
-
想请问一下作者,为什么这里是O(n)
|
Beta Was this translation helpful? Give feedback.
-
上一讲说平均时间复杂度不好计算,时间复杂度实际取的是渐近上界,即最差时间复杂度,所以和空间复杂度不是一样么?都是最差。我理解错了? |
Beta Was this translation helpful? Give feedback.
-
你好,图 2-18中所述的空间复杂度为什么不考虑递归所产生的n个函数?麻烦解答下 |
Beta Was this translation helpful? Give feedback.
-
大O计算的是趋势,而不是具体的次数呀
在 2024年2月18日星期日,Yudong Jin ***@***.***> 写道:
… Hi,递归使用的栈帧空间的空间复杂度是 $O(n)$,比数组使用的 $O(n^2)$ 空间更小,因此可以省略统计。
—
Reply to this email directly, view it on GitHub
<#19 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AO42YQBCVJX7QIAPUYGWLZDYUDYURAVCNFSM6AAAAAASLISPNKVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DKMBSGMZDC>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
K神您好!想问一下,这段代码的任务是什么呀?
|
Beta Was this translation helpful? Give feedback.
-
这一章解释的太清楚啦!感觉回过头要常复习。
|
Beta Was this translation helpful? Give feedback.
-
想问一问用递归方法求解斐波那契数列的空间复杂度是多少呢? |
Beta Was this translation helpful? Give feedback.
-
在“如图 2-18 所示”那段话中,后面说平均长度是n/2是不是说错了 应该是n(n+1)/2 |
Beta Was this translation helpful? Give feedback.
-
对数阶那里,归并排序的空间复杂度是O(n)吧?因为每一层在向上归的时候都把临时申请的空间释放了,最大也不超过n |
Beta Was this translation helpful? Give feedback.
-
2.4.1, 2.4.2 的 zig 代码是空白啊 |
Beta Was this translation helpful? Give feedback.
-
2-19,虽然递归调用栈的深度是 O(n),但是创建的节点数量O(n^2)才是主要的空间消耗。 |
Beta Was this translation helpful? Give feedback.
-
感觉空间复杂度还是不太理解,先看看后续再回顾一下 |
Beta Was this translation helpful? Give feedback.
-
有点懵懵的😳。后面再回来看看 |
Beta Was this translation helpful? Give feedback.
-
图2-18平方阶运算时不考虑栈帧空间n吗,是因为考虑最差才省去的吧 |
Beta Was this translation helpful? Give feedback.
-
还是得反复看和练习 |
Beta Was this translation helpful? Give feedback.
-
抓个虫,2.4.3中线性阶的代码注释,是链表不是列表吗? |
Beta Was this translation helpful? Give feedback.
-
int function() { |
Beta Was this translation helpful? Give feedback.
-
chapter_computational_complexity/space_complexity/
动画图解、一键运行的数据结构与算法教程
https://www.hello-algo.com/chapter_computational_complexity/space_complexity/
Beta Was this translation helpful? Give feedback.
All reactions