6

当我遇到在对象中查找的答案range之一是 CONSTANT TIME 操作时，我正在滚动浏览 StackOverflow 上的许多列表与范围相关的问题！如何在 O(1) 中完成这是没有意义的，您将不得不遍历该范围以查看是否存在数字。范围对象是否像一些哈希图/字典一样工作？

def usingRange(x):
    return x in range(0, 100000000)
print(usingRange(9999999)) 


def noRange(x):
    return x in list(range(0, 100000000))
print(noRange(9999999))

%timeit usingRange(9999999)
%timeit noRange(9999999)

我得到的输出为：

True
True
443 ns ± 8.83 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
6.89 s ± 380 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

我想知道为什么它的时间恒定是因为

  1. 有人告诉我不要太专注于在 Python 中学习编程面试的“技巧”！因为你所做的一切，你都必须解释时间复杂度，所以你要么记住i in list1O(N)，要么使用 for 循环遍历列表：

    for j in range(len(list1)):
    if list1[j] == i:
        print(True)

else:
    print(False)

然后得出结论，它实际上是 O(N) 因为要检查一个元素是否存在，你必须遍历列表的每个元素直到列表的末尾（最坏的情况）。但是一些常数时间运算似乎不那么明显！我可以接受这样一个事实，即哈希表中的循环是 O(1)，因为有一个名为 Hashing 的大概念（尚未讨论过），但不确定它如何用于range对象。

  1. 有人告诉我，了解基础知识至关重要！并尽力解释你所写内容的每一行以及为什么要在白板上写。我认识的某个人被要求为一家非常有名的科技公司的 SWE 职位实施 HASHMAP。

  2. 我有很多时间（1 年）来准备和好奇。

4

0 回答 0