作者Rioronja (Rioronja)
看板Grad-ProbAsk
标题[理工] 资结 Inplace
时间Wed Feb 27 13:24:54 2019
到底什麽是inplace
记得当初写考古的时候也有看到这个字
上网查了资料
却都没有清楚定义
有没有能抽丝剥茧一下inplace的概念
今年好多学校都有考这个
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.254.34.219
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1551245097.A.CF4.html
1F：推 Dora5566: 在原本input空间用交换的方式排序 02/27 13:33
2F：→ Rioronja: Dora大 可是我看有人写说QuickSort不是in place的 02/27 13:33
3F：推 wilson50101: sorting in place就是只说只靠原来input的资料结构的 02/27 13:34
4F：→ Dora5566: 会考这个的学校都已经考完了 02/27 13:34
5F：→ wilson50101: 空间来做swap而完成排序 02/27 13:34
6F：→ wilson50101: 不需要依靠另外的空间完成 02/27 13:34
7F：→ wilson50101: eg inplace有quicksort heapsort等 02/27 13:34
8F：→ wilson50101: not inplace有mergesort 02/27 13:34
9F：→ Rioronja: 可是他是实作SWAP来排序的啊 02/27 13:34
10F：→ wilson50101: quicksort是inplace 因为他的额外空间是靠递回的stac 02/27 13:35
11F：→ wilson50101: k产生的跟排序无关 02/27 13:35
12F：→ Rioronja: 了解！！所以可以定义说如果是用SWAP来SORTING的 02/27 13:36
13F：→ Rioronja: 都是inplace的吧ㄥ 02/27 13:36
14F：推 Dora5566: 不是吧 不是用SWAP就会是inplace 02/27 13:39
15F：→ Dora5566: 是inplace只能用SWAP 02/27 13:39
18F：→ Rioronja: 我考前看维基百科里面，确实把Quick定义成非inplace 02/27 13:43
19F：→ Rioronja: 对！Dora大跟我看得一样，所以Quicksort怎麽分类啊！！ 02/27 13:44
20F：推 wilson50101: 补习的时候洪逸老师是讲quicksort是inplace 02/27 13:45
21F：→ wilson50101: 可能这部分有争议吧我觉得 02/27 13:45
22F：→ Rioronja: 看来要去看原文书了 不过我那时候翻原文书怎麽没看到 02/27 13:47
23F：→ Rioronja: inplace的定义啊 02/27 13:47
24F：推 Dora5566: 这个最好是去查学校的ptt 毕竟改考卷的是教授 02/27 13:51
25F：→ Dora5566: 我本来也以为quicksort是inplace 现在看起来我也不知道 02/27 13:52
26F：→ Dora5566: 惹 02/27 13:52
27F：→ Rioronja: 照百科上的定义，只要要用到递回的演算法，因为至少要用 02/27 13:58
28F：→ Rioronja: 一个Stack来追踪，所以就不是inplace。 02/27 13:58
29F：→ Rioronja: 看很多人则是在意在排序过程中，有没有使用额外空间 02/27 13:59
30F：推 TWkobe: 这定义蛮无聊的 你用linked list实作还会in place？ 02/27 16:44
31F：推 hodo: 感觉着重的点是有无额外空间？就是空间复杂度 02/27 18:01
33F：→ yp195126: 台大那题基准为最右 看起来应该是True? 02/27 20:57
34F：→ Rioronja: 楼上大大们 我看各个网路上的分类，有的是以上面说的空 02/27 22:31
35F：→ Rioronja: 间复杂度去做判别的，也有是说因为quick一定会用到递回 02/27 22:31
36F：→ Rioronja: ，递回使用额外的资料结构也就是stack来协助运作，所以 02/27 22:31
37F：→ Rioronja: 非in place。症结点应该在是在sorting 的中间来看，还是 02/27 22:31
38F：→ Rioronja: 以整个实作面来看。说实在的，讨论这个很无聊，又不会因 02/27 22:31
39F：→ Rioronja: 为我们定义他是不是in place实作上会有差异，也没有in p 02/27 22:31
40F：→ Rioronja: lace额外会附带什麽性质，纯粹是考题考出来一翻两瞪眼， 02/27 22:31
41F：→ Rioronja: 事前有做准备也会因为个人观点不同而相左。纯粹碎念～ 02/27 22:31
44F：推 ekids1234: 洪毅说 inplace ? 可是笔记我在看的时候写需递回 02/28 02:16
45F：→ ekids1234: 就想说洪毅应该也认为不是 .. ? 02/28 02:17
46F：→ hodo: cute大，给的图是说插入排序是inplace吧？还说看错了 02/28 02:42
47F：→ cutearia: 第一张是quick的partition 第二张是in place定义 02/28 06:27
49F：→ cutearia: 补一下 贴16页的原因 觉得考试照枫叶比较好 02/28 06:36
50F：推 hodo: 是说quicksort有分有无inplace的版本 就看教授认为是哪个了 02/28 07:41
51F：→ hodo: 吧.. 然後额外用logn 太小就可以忽略 说是inplace的样子? 02/28 07:41
52F：推 xcnx123: 只用到额外O(1)空间的就是inplace，依照这标准去算就可以 03/05 21:18
53F：→ xcnx123: 判断了 03/05 21:18