楼主:
cccict (马路柏油)
2021-08-17 01:40:44刚刚编辑文章按到复原草稿
插入很多不必要东西
但用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)一定不对
他很肯定说这样做答案绝对不是线性的
想请问这样计算时间复杂度到底哪里有问题
谢谢
作者: sjensen (KwonIn) 2021-08-17 02:09:00
两个loop分开怎么不会是线型的，不解+1
作者: charle0911 2021-08-17 02:54:00
不专业回答：HashMap广义来说都是O(1)碰撞之后才会用红黑树实践排列碰撞的元素 当Hash array足够大时红黑树的成本可以不计 广义是这样 若有错请高手指点迷津不过你po的程式码O(m+n)完全没毛病 不知面试官的思路是怎样为何会觉得不是
作者:
sorryla (Mr.东)
2021-08-17 04:28:00你应该当场反问哪里不对的，搞不好是面试官自己根本不懂
作者:
wawi2 (@@)
2021-08-17 06:41:00面试官搞错的机率很大 也有可能你们的沟通有一些误会move on就可以了
作者:
shiauji (消極)
2021-08-17 06:55:00面试官大概把TreeMap and HashMap搞错了吧
作者: NciscalA 2021-08-17 07:05:00
c++ 的 std::set 不是 hash map ，std::unorderd_map才是噢。不过前面 O(m+n) 看起来没什么问题。啊是 std::map 不是 std::set
c++ 的map （TreeMap)vs unordered map(HashMap)前者强调有序所以会用RBTree就会多了log复杂度，后者大Hash 表查询O(1) 但有碰撞好像另当别论，不过机率低，Amortized 应该仍是O(1)，有误欢迎指正
作者: aa06697 (todo se andarà) 2021-08-17 08:39:00
O(m+n)吧 但如果面试官说错的话 我会问他是因为hash collision吗
作者:
sooge (老衲)
2021-08-17 09:00:00不是线性的话就是nlogn了吧 面试官一定想到红黑树了
作者:
yyc1217 (somo)
2021-08-17 09:18:00面试官搞错了
作者: eigen555 (一一一) 2021-08-17 09:40:00
unordered map发生严重碰撞的话 搜寻的worst case 是 O(m)average case才是O(1)
作者: zenithyoung 2021-08-17 11:28:00
O(m+n) +1
这面试官不太行啊 不过建议你可以问下数据大小 如果面试官说数据量很大 那你可以说有碰撞问题 如果不是那你可以选别家公司了
作者:
pttano (pttano)
2021-08-17 18:19:00这间面试官程度太差了
南港面过做手机的公司 主管也是坚持hash search notO(1)
面试官只是希望你说一下worst case而已吧 我感觉面试的时候被要求分别提一下worst case跟average case的情况还蛮常见的啊
作者:
MyNion (Nion Lee)
2021-08-17 21:58:00O(n+m) +1，除非每一个插进HashSet的元素都杂凑碰撞才会让复杂度变成O(n*m)那面试官的主观意识感觉过强+不善沟通，雷雷的不去也罢
也有可能是问worse case 或者现场的程式码不一样
作者:
jolyoy (Northan)
2021-08-18 01:04:00已经在讨论时间复杂度了，应该都是用最基本的资料结构，先入为主用unordered map来算，其实也有问题，一定是双方没沟通清楚
作者:
wulouise (在线上!=在电脑前)
2021-08-18 07:20:00我觉得说人错，到最后都没给提示算是面试官问题
我看过几本中国的面试刷题书 分析hash table的timecomplexity都会要求面试者要特别提一下运气极差所有key都collision的情况跟一般情况 我猜那个主管大概也是看过类似的书 所以默认你应该要回答..
作者:
jlhc (H)
2021-08-19 22:03:00你的实作就是线性...面试官也是人 面试官搞错的可能性也是有的
作者: rems (rems) 2021-08-20 23:30:00
其实讨论Big O我觉得就是在讲worst case了我倒觉得科班出身念过算法的会答linear time很奇怪...
c++ 的 unordered_set 默认的 hash function 很容易造出让他全部 collision 的状况，所以要更干净还得自制乱数更均匀的 hash function，但感觉上不是在考这个...不过真遇到这种面试官自己搞不清楚状况的时候，就是把你所有知道的底层知识都搬出来跟他讨论一遍就对了，看是他会突然发现自己搞错，或是你突然打中他某个神祕的想听得关键点，你就会过了
M+n哪里不对 又不是nested loop 面试官不要不懂装懂欸
作者: rems (rems) 2021-08-23 22:59:00
我只能说algorithm课本是好东西，可以多念一下要讨论实作这样写没什么问题但是如果是要讨论time complexity回linear真的比较外行去查一下大O小o还有omegabig O就是在讨论worst case建立一组O(1)? 查询O(1)? 不懂不要装懂
照楼上的说法 一堆排序例如quicksort应该是O(n^2)