已知M个数，长度为N的黑名单，查找这M个数是否在黑名单中，对简单的遍历查找（不对黑名单排序），问时间复杂度是多少？
我认为是M*N, 同事说是N^2
:lol: 那个对？
O(m*n)
我觉得应该是m*n吧，m个数都遍历n次=m*n
o(m+n)
最小的时间复杂度是O(m+n)，方法是为长度为N的黑名单建立一个一个Hash表，复杂度为N，然后对m个数字在Hash表里面进行查找，由于Hash表的复杂度为O(1),因此m个数字的复杂度为O(n)，因此得出的结论为O(m+n)
同意这个说法：
最小的[url=http://www.01yun.com/gu_import_search.jspx?q=时间复杂度]时间复杂度[/url]是O(m+n)，方法是为长度为N的黑名单建立一个一个Hash表，复杂度为N，然后对m个数字在Hash表里面进行查找，由于Hash表的复杂度为O(1),因此m个数字的复杂度为O(n)，因此得出的结论为O(m+n)
参见：[url=http://www.01yun.com/other/20130426/382343.html]http://www.01yun.com/other/20130426/382343.html[/url]