剛剛編輯文章按到復原草稿
插入很多不必要東西
但用Pitt沒辦法編輯
所以刪除重po不好意思
以下代之前社團認識的學妹代po詢問
我是今年畢業的新鮮人
今天面試白板考的時候考了跟差集有關的問題
關於時間複雜度的部分怎麼想都想不通
已經查過資料也跟要考資工所的朋友、資工系的朋友討論過
仍然不確定答案，想請版上大神開示一下：D
題目：有A、B兩個未經排序的array
A有n個整數，B有m個整數
寫一個function回傳在A且不在B的整數。
(皆先不討論A、B內各自有重複元素的情況)
我的做法：
1.先把B的每個元素放進dictionary
2.然後用for檢查A的每個元素是否為dictionary的key，不是的話就加入ans的list
3.回傳ans
想以python的dictionary來討論這題的時間複雜度
用B建立長度為m的dictionary
新增一組key-value時間複雜度是O(1)；A的長度為n
查找是否在dictionary的key時的時間複雜度是O(1)
我覺得時間複雜度是O(m+n)。
參考leetcode簡中板的類似題目的官方詳解(只有簡中版討論區有官方詳解)
https://reurl.cc/KAaRmy
leetcode這題基本一樣
是找出在A且在B的整數
官方是用set來實作
時間複雜度是O(m+n)
想請問dictionary和set()底層的hash原理會是造成時間複雜度不同的關鍵嗎？
Python程式碼如下
def solution(A:List[int], B:List[int]):
ans = []
dic = dict()
for b in B:
dic[b] = b
for a in A:
if a not in dic:
ans.append(a)
return ans
另外，我知道hash在python以外的語言像是C/C++
若是基於紅黑樹來實做的話
時間複雜度會是O(nlogm)。
我想問的是python的時間複雜度！
補充
想知道答案是因為
面試官說我的答案O(m+n)一定不對
他很肯定說這樣做答案絕對不是線性的
想請問這樣計算時間複雜度到底哪裡有問題
謝謝

O(m+n)是對的吧

兩個loop分開怎麼不會是線型的，不解+1

不專業回答：HashMap廣義來說都是O(1)碰撞之後才會用紅黑樹實踐排列碰撞的元素 當Hash array足夠大時紅黑樹的成本可以不計 廣義是這樣 若有錯請高手指點迷津不過你po的程式碼O(m+n)完全沒毛病 不知面試官的思路是怎樣為何會覺得不是

你應該當場反問哪裡不對的，搞不好是面試官自己根本不懂

面試官搞錯的機率很大 也有可能你們的溝通有一些誤會move on就可以了

面試官大概把TreeMap and HashMap搞錯了吧

c++ 的 std::set 不是 hash map ，std::unorderd_map才是噢。不過前面 O(m+n) 看起來沒什麼問題。啊是 std::map 不是 std::set

O(m+n) 一票

再一票O(m+n)

c++ 的map （TreeMap)vs unordered map(HashMap)前者強調有序所以會用RBTree就會多了log複雜度，後者大Hash 表查詢O(1) 但有碰撞好像另當別論，不過機率低，Amortized 應該仍是O(1)，有誤歡迎指正

O(m+n)吧 但如果面試官說錯的話 我會問他是因為hash collision嗎

不是線性的話就是nlogn了吧 面試官一定想到紅黑樹了

面試官搞錯了

unordered map發生嚴重碰撞的話 搜尋的worst case 是 O(m)average case才是O(1)

面試官沒解釋自己的思路 感覺有點雷R

O(m+n) +1

這面試官不太行啊 不過建議你可以問下數據大小 如果面試官說數據量很大 那你可以說有碰撞問題 如果不是那你可以選別家公司了

這間面試官程度太差了

南港面過做手機的公司 主管也是堅持hash search notO(1)

面試官只是希望你說一下worst case而已吧 我感覺面試的時候被要求分別提一下worst case跟average case的情況還蠻常見的啊

O(n+m) +1，除非每一個插進HashSet的元素都雜湊碰撞才會讓複雜度變成O(n*m)那面試官的主觀意識感覺過強+不善溝通，雷雷的不去也罷

也有可能是問worse case 或者現場的程式碼不一樣

已經在討論時間複雜度了，應該都是用最基本的資料結構，先入為主用unordered map來算，其實也有問題，一定是雙方沒溝通清楚

我覺得說人錯，到最後都沒給提示算是面試官問題

我看過幾本中國的面試刷題書 分析hash table的timecomplexity都會要求面試者要特別提一下運氣極差所有key都collision的情況跟一般情況 我猜那個主管大概也是看過類似的書 所以預設你應該要回答..

溝通不良吧 如果如原PO所言 面試官責任較大https://wiki.python.org/moin/TimeComplexity

你的實作就是線性...面試官也是人 面試官搞錯的可能性也是有的

其實討論Big O我覺得就是在講worst case了我倒覺得科班出身念過演算法的會答linear time很奇怪...

c++ 的 unordered_set 預設的 hash function 很容易造出讓他全部 collision 的狀況，所以要更乾淨還得自製亂數更均勻的 hash function，但感覺上不是在考這個...不過真遇到這種面試官自己搞不清楚狀況的時候，就是把你所有知道的底層知識都搬出來跟他討論一遍就對了，看是他會突然發現自己搞錯，或是你突然打中他某個神祕的想聽得關鍵點，你就會過了

M+n哪裡不對 又不是nested loop 面試官不要不懂裝懂欸

我只能說algorithm課本是好東西，可以多念一下要討論實作這樣寫沒什麼問題但是如果是要討論time complexity回linear真的比較外行去查一下大O小o還有omegabig O就是在討論worst case建立一組O(1)? 查詢O(1)? 不懂不要裝懂

照樓上的說法 一堆排序例如quicksort應該是O(n^2)