반복이 더 많은 경우에도 한 코드가 다른 것보다 왜 더 빠릅니까?

Question

내 코드가 짧고 반복 횟수가 적지 만 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() 

빨리 :이 코드는 왜 코드는 codechef.com 에서 "모호한 순열"문제에 대한 솔루션입니다

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")  

이 저를 도와주세요 ...

Answer 1

이러한 일관된 시간 차이가 나타나면 우리는 2 또는 3 배 느린 것을 말하지 않습니다. 한 가지 방법이 통과하고 다른 하나는 항상 타임 아웃하면, 그것은 엄청난 시간 차이입니다. 알고리즘 복잡성.

첫 번째 코드에는 더 많은 공간 (예 : 범위 대신 xrange 사용)이 있지만 최종 배열의 결과는 data[i] - 1의 색인에 의해 무작위 액세스로 업데이트됩니다. 두 번째 발췌 문장에서는 caseList.index(str(i))을 사용하여 각 색인을 검색합니다. "index"lisr 메서드는 처음부터 목록에서 선형 검색을 수행합니다. 그것은 거의 보이지 않을 수도 있지만 목록의 각 요소에 대해 doen 일 때 O (N) 인 알고리즘은 O (N²)가됩니다.이 두 번째 형식에서는 극적인 속도가 줄어 듭니다.

Answer 2

두 번째 코드는 함수 안에 들어 있지 않습니다.

함수에서 지역 변수에 액세스하는 것이 전역 변수에 액세스하는 것보다 훨씬 빠릅니다. 즉, 전역 범위에서 실행되는 코드는 항상 느려질 수 있습니다.

Answer 3

다른 코드가 int를 사용하는 문자열을 사용하고있는 것처럼 보입니다. 그러면 약간 느려질 것입니다.