推 jumbotest:偶像 01/19 21:09
※ 引述《jumbotest (Ukulele)》之銘言：
: 是非題:
: Removing the tail in a singly linked list takes O(1) time.
: Sol: (X) 是O(n)
: 我查到的說法是 刪除尾端要從頭找到尾
: 所以時間複雜度同查找節點 也就是O(n)
這段是對的
因為是用指標去把node串聯
在記憶體的空間裡不一定是連續配置的
所以它"指定"刪最後一個node 而這個linked list是singy
必須要從head一路search到尾 花O(n)
: 可是我記得linked-list相較array插入與刪除比較快
: 所以array的插入刪除是O(n)
: linked-list是0(1)嗎?
: 到底linked-list刪除節點的時間複雜度是多少啊...!!!
刪除node 只要改指標而已
只需O(1)
這題最主要的時間是花在search上
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.26.80