字典运行时(Codility Test)

Question

我尝试了一个codility示例问题,在python中回答.我没有得到100分,因为它未能及时完成大数据集.

以下是问题:

给出了由N个整数组成的非空零索引数组A. 数组A的第一个覆盖前缀是最小整数P,使得0≤P<N并且使得在数组A中出现的每个值也出现在序列A [0],A [1],...,A [P中].

例如,以下5元素数组A的第一个覆盖前缀:

A[0] = 2  A[1] = 2  A[2] = 1
A[3] = 0  A[4] = 1

是3,因为序列[ A[0], A[1], A[2], A[3] ]等于[2, 2, 1, 0],包含在数组A中出现的所有值.

我的回答是:

def ps ( A ):
    N = len(A);
    if N == 0: return -1
    bit = {}
    for i in range(N):
        if not A[i] in bit.keys():
            bit[A[i]] = 1
            P = i
    return P

结果:

它没有给我100这个问题因为它认为我的算法是O(N**3),并且测试用例失败了

random_n_log_100000 
random test 100 000 elements and n/log_2 n values.  10.025 s.   TIMEOUT ERROR 
running time: >10.02 sec., time limit: 9.82 sec.

random_n_10000 
random test 10 000 elements and values. 1.744 s.    TIMEOUT ERROR 
running time: >1.74 sec., time limit: 1.10 sec.

random_n_100000 
random test 100 000 elements and values.    10.025 s.   TIMEOUT ERROR 
running time: >10.02 sec., time limit: 9.94 sec.

分析:

1. 起初我认为我的代码是O(N),因为我假设代码的关键部分,bit.keys()中的A [i]具有恒定的运行时,即O(1).但也许在大型数据集上,哈希函数会产生很多冲突,因此运行时不再是O(1)？

2. O(N**3)是否意味着O(N ^ 3)？我有这个问题,因为我已经看到其他帖子,其中codility报告N平方算法为O(N ^ 2).所以我想他们的报告会一致吗？

3. 如果他们真的认为我的答案是O(N ^ 3),那么它是否合理是因为我的代码只超过了他们的时间限制不到1秒？在这里,我假设他们的时间限制是O(N)算法,因为这是他们在问题中要求的.如果是这种情况,我不明白为什么O(N ^ 3)算法只是> 1秒慢？

Answer 1

bit.keys()是一个清单.测试元素是否在列表中是O(n).另一方面,测试元素是否在dict中是O(1).所以改变

if not A[i] in bit.keys():

至

if not A[i] in bit:

有了这个改变,我相信你的算法是O(n).

(没有改变,我相信你的算法是O(n ^ 2),而不是 O(n ^ 3).)