时间复杂度

问题描述

已知M个数，长度为N的黑名单，查找这M个数是否在黑名单中，对简单的遍历查找（不对黑名单排序），问时间复杂度是多少？我认为是M*N, 同事说是N^2 那个对？

解决方案

O(m*n)
解决方案二：
同意这个说法：最小的时间复杂度是O(m+n)，方法是为长度为N的黑名单建立一个一个Hash表，复杂度为N，然后对m个数字在Hash表里面进行查找，由于Hash表的复杂度为O(1),因此m个数字的复杂度为O(n)，因此得出的结论为O(m+n)参见：http://www.01yun.com/other/20130426/382343.html
解决方案三：
最小的时间复杂度是O(m+n)，方法是为长度为N的黑名单建立一个一个Hash表，复杂度为N，然后对m个数字在Hash表里面进行查找，由于Hash表的复杂度为O(1),因此m个数字的复杂度为O(n)，因此得出的结论为O(m+n)
解决方案四：
o(m+n)
解决方案五：
我觉得应该是m*n吧，m个数都遍历n次=m*n