[理工] big O()以及"can be"這種題目敘述

[sjdijojdj (Leo)]

我舉幾題104台大電機丙的題目當例子

1.Given two linked list，its deletion operation can be O(logn)

我自己覺得這個應該是True，O(logn)應該可以包含O(1)

2.The height of a Binomial Heap of n nodes can be O(n)

我也覺得是True，理由同上

3.Given a fixed size array，the time complexity to remove the minimum
element can be O(1)

題目沒有說它是不是sorted，如果是由大到小排好的話，直接砍掉最後一個就可以在
O(1)內完成了，所以他說can be我也覺得是對的

想問一下，我這樣會太執著在can be這種字眼上嗎?

還是題目原本就是要這樣考的?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.200.12 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1575954350.A.B18.html
→ DLHZ: 常數時間在O(n)內沒問題 3.我也是同樣的想法
推 louis117228: 既然題目沒講，為什麼你們會假設array可能sorted？
→ louis117228: 所以我覺得3是錯
→ DLHZ: 我改變心意了XD 原本想法是 有可能剛好是sort 那直接刪就好
→ DLHZ: 但如果要這樣 有個問題是並不知道輸入的陣列是不是 變成要對
→ DLHZ: 每個輸入的陣列都做刪掉最後一個這件事 但這樣應該就錯了
推 mistel: 真心好奇有沒有台大電機丙的同學有問過老師是希望看到什
→ mistel: 麼回答