3

我的代码很短，迭代次数比另一个代码少，但它仍然会出现超出时间限制的错误，而其他代码在 codechef.com 上被接受。这些代码是 codechef.com 上“模糊排列”问题的解决方案 为什么这个代码：

def inverse(data,x):

    temp=[]

    for i in range(x):
        temp.append(0)
    for i in range(x):
        temp[data[i]-1]=i+1
    return temp

def main():

    while 1:
        x=input()
        if not x:
            return
        data=raw_input().split(' ')
        for i in range(len(data)):
            data[i]=int(data[i])
        temp = inverse(data,x)
        if temp==data:
            print 'ambiguous'
        else:
            print 'not ambiguous'

if __name__ == "__main__":
    main()

比这段代码快：

while True:

    output=[]
    n= input()
    if n==0: break
    caseList= raw_input().split()
    amb=1
    for i in range(1, n+1):
        output.append(str(caseList.index(str(i))+1))

    if output==caseList:
        print ("ambiguous")
    else:
        print ("not ambiguous")

请帮帮我...

4

3 回答 3

3

我认为您的第二个代码不在函数内。

访问函数中的局部变量比访问全局变量要快得多。这意味着在全局范围内运行的代码总是可能更慢。

于 2012-03-01T20:32:04.887 回答
2

当出现这种一致的时间差时，我们不是在谈论慢 2 或 3 倍的东西——如果一种方法通过，而另一种方法总是超时，这是一个巨大的时间差——通常与算法复杂性有关。

尽管第一个代码有很大的改进空间（例如，使用 xrange 而不是 range），但在最终数组中，结果是通过随机访问更新的，直接由计算的索引data[i] - 1- 而在第二个片段中，您用于caseList.index(str(i))检索每个索引。"index" lisr 方法对列表执行线性搜索，从开头开始。它可能看起来很少，但是当它为列表中的每个元素执行时，你的算法 O(N) 变成了 O(N²) - 这解释了第二种形式的显着速度下降。

于 2012-03-02T05:19:57.180 回答
1

看起来您正在使用字符串，而其他代码正在使用整数，这会降低您的速度。

于 2012-03-01T20:37:38.533 回答