[請益] 面試白板考題目的時間複雜度

[cccict (馬路柏油)]

剛剛編輯文章按到復原草稿
插入很多不必要東西
但用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)一定不對
他很肯定說這樣做答案絕對不是線性的
想請問這樣計算時間複雜度到底哪裡有問題
謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.250.114 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1629135646.A.93D.html
推 mimi9126: O(m+n)是對的吧
→ sjensen: 兩個loop分開怎麼不會是線型的，不解+1
→ charle0911: 不專業回答：HashMap廣義來說都是O(1)碰撞之後才會用
→ charle0911: 紅黑樹實踐排列碰撞的元素 當Hash array足夠大時紅黑
→ charle0911: 樹的成本可以不計 廣義是這樣 若有錯請高手指點迷津
→ charle0911:  不過你po的程式碼O(m+n)完全沒毛病 不知面試官的思
→ charle0911: 路是怎樣為何會覺得不是
推 sorryla: 你應該當場反問哪裡不對的，搞不好是面試官自己根本不懂
→ wawi2: 面試官搞錯的機率很大  也有可能你們的溝通有一些誤會
→ wawi2: move on就可以了
推 shiauji: 面試官大概把TreeMap and HashMap搞錯了吧
推 NciscalA: c++ 的 std::set 不是 hash map ，std::unorderd_map
→ NciscalA: 才是噢。不過前面 O(m+n) 看起來沒什麼問題。
→ NciscalA: 啊是 std::map 不是 std::set
推 WaterLengend: O(m+n) 一票
推 aspwell520: 再一票O(m+n)
推 Amazonite96: c++ 的map （TreeMap)vs unordered map(HashMap)前
→ Amazonite96: 者強調有序所以會用RBTree就會多了log複雜度，後者大
→ Amazonite96: Hash 表查詢O(1) 但有碰撞好像另當別論，不過機率低
→ Amazonite96: ，Amortized 應該仍是O(1)，有誤歡迎指正
→ aa06697: O(m+n)吧 但如果面試官說錯的話 我會問他是因為hash coll
→ aa06697: ision嗎
推 sooge: 不是線性的話就是nlogn了吧 面試官一定想到紅黑樹了
→ yyc1217: 面試官搞錯了
推 eigen555: unordered map發生嚴重碰撞的話 搜尋的worst case 是 O(
→ eigen555: m)
→ eigen555: average case才是O(1)
推 DarkIllusion: 面試官沒解釋自己的思路 感覺有點雷R
推 zenithyoung: O(m+n) +1
推 jass970991: 這面試官不太行啊 不過建議你可以問下數據大小 如果
→ jass970991: 面試官說數據量很大 那你可以說有碰撞問題 如果不是
→ jass970991: 那你可以選別家公司了
推 pttano: 這間面試官程度太差了
推 TheOneisNEO: 南港面過做手機的公司 主管也是堅持hash search not
→ TheOneisNEO: O(1)
推 Parazicecum: 面試官只是希望你說一下worst case而已吧 我感覺面試
→ Parazicecum: 的時候被要求分別提一下worst case跟average case的
→ Parazicecum: 情況還蠻常見的啊
推 MyNion: O(n+m) +1，除非每一個插進HashSet的元素都雜湊碰撞
→ MyNion: 才會讓複雜度變成O(n*m)
→ MyNion: 那面試官的主觀意識感覺過強+不善溝通，雷雷的不去也罷
→ cha122977: 也有可能是問worse case 或者現場的程式碼不一樣
推 jolyoy: 已經在討論時間複雜度了，應該都是用最基本的資料結構，
→ jolyoy: 先入為主用unordered map來算，其實也有問題，一定是雙方
→ jolyoy: 沒溝通清楚
→ wulouise: 我覺得說人錯，到最後都沒給提示算是面試官問題
推 Parazicecum: 我看過幾本中國的面試刷題書 分析hash table的time
→ Parazicecum: complexity都會要求面試者要特別提一下運氣極差所有
→ Parazicecum: key都collision的情況跟一般情況 我猜那個主管大概也
→ Parazicecum: 是看過類似的書 所以預設你應該要回答..
推 s0914714: 溝通不良吧 如果如原PO所言 面試官責任較大
推 s0914714: https://wiki.python.org/moin/TimeComplexity
推 jlhc: 你的實作就是線性...
→ jlhc: 面試官也是人 面試官搞錯的可能性也是有的
→ rems: 其實討論Big O我覺得就是在講worst case了
→ rems: 我倒覺得科班出身念過演算法的會答linear time很奇怪...
推 BBSealion: c++ 的 unordered_set 預設的 hash function 很容易造
→ BBSealion: 出讓他全部 collision 的狀況，所以要更乾淨還得自製
→ BBSealion: 亂數更均勻的 hash function，但感覺上不是在考這個...
→ BBSealion: 不過真遇到這種面試官自己搞不清楚狀況的時候，就是把
→ BBSealion: 你所有知道的底層知識都搬出來跟他討論一遍就對了，看
→ BBSealion: 是他會突然發現自己搞錯，或是你突然打中他某個神祕的
→ BBSealion: 想聽得關鍵點，你就會過了
推 imjeffreylee: M+n哪裡不對 又不是nested loop 面試官不要不懂裝懂
→ imjeffreylee: 欸
→ rems: 我只能說algorithm課本是好東西，可以多念一下
→ rems: 要討論實作這樣寫沒什麼問題
→ rems: 但是如果是要討論time complexity回linear真的比較外行
→ rems: 去查一下大O小o還有omega
→ rems: big O就是在討論worst case
→ rems: 建立一組O(1)? 查詢O(1)? 不懂不要裝懂
推 s0914714: 照樓上的說法 一堆排序例如quicksort應該是O(n^2)
→ peter98: 回頭看到這篇 rems是真的很外行  worst case跟big-O沒什
→ peter98: 關係  big-O也可以用在best case和avg case