103成大資結

看板Grad-ProbAsk作者 (Butterlion)時間9年前 (2017/01/10 18:00), 編輯推噓3(3推 0噓 15→)
留言18則, 7人參與, 最新討論串1/1
http://i.imgur.com/OiN1br7.jpg
我覺得是O(log n) 為什麼會是O(n) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.138.77.64 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484042412.A.86C.html
推
01/10 18:07, , 1F
我的想法是先把三個sorted array merge起來成一個
01/10 18:07, 1F
→
01/10 18:08, , 2F
需要O(n)，然後最中間當root，切成左右兩堆
01/10 18:08, 2F
→
01/10 18:08, , 3F
再遞迴做下去，每次遞迴就是把中間那個挑出來當root就
01/10 18:08, 3F
→
01/10 18:09, , 4F
好，所以T(n)=2T(n/2)+O(1)，T(n)=O(n)
01/10 18:09, 4F
→
01/10 18:15, , 5F
有點好奇原po的作法是如何達到O(logn)的
01/10 18:15, 5F
→
01/10 18:18, , 6F
Merge無誤
01/10 18:18, 6F
→
01/10 18:26, , 7F
問一下balanced binary search tree是AVL tree嗎?
01/10 18:26, 7F
→
01/10 18:27, , 8F
因為AVL tree就是O(logn)了
01/10 18:27, 8F
→
01/10 18:33, , 9F
AVL tree也是一種balanced binary search tree，那麼
01/10 18:33, 9F
→
01/10 18:33, , 10F
要如何達到logn呢？
01/10 18:33, 10F
→
01/10 19:00, , 11F
我想說AVL都是O(log n) 哈哈
01/10 19:00, 11F
→
01/10 19:06, , 12F
可是他這邊是要建一個tree，建一個AVL應該不是O(logn)?
01/10 19:06, 12F
→
01/10 19:19, , 13F
建AVL tree要nlogn
01/10 19:19, 13F
推
01/10 22:42, , 14F
從 sorted array 建 balanced BST 只要 O(n)
01/10 22:42, 14F
推
01/11 07:39, , 15F
sorted array用merge建balance tree也是O(nlogn)? 那用
01/11 07:39, 15F
→
01/11 07:39, , 16F
insertion或bubble sort 不也可以達到O(n)?
01/11 07:39, 16F
→
01/11 07:43, , 17F
看錯..他是要建tree..
01/11 07:43, 17F
→
01/11 09:40, , 18F
balanced bst 就是avl的一種... 請忽略我上面的留言XD
01/11 09:40, 18F
‣ 更多 kkk22805385 的文章
文章代碼(AID): #1OTB2iXi (Grad-ProbAsk)