Python Script : O (N) 또는 O (N^2) 시간을 확인하는 방법은 무엇입니까?

코드가 O (N) 시간 (선형 시간?) 또는 O (N^2) 시간 또는 다른 것에서 실행되는지 어떻게 알 수 있습니까? 연습은 오랫동안 계산 시간이 오래 걸리는 코드에 대한 온라인 도킹 포인트를 테스트합니다.Python Script : O (N) 또는 O (N^2) 시간을 확인하는 방법은 무엇입니까?

실행하는 데 걸리는 시간이 입력 데이터 길이 (O (N) 시간)에 비례하는 스크립트를 사용하는 것이 가장 좋음을 알고 있으며 이것이 내 코드인지 확인합니다. 하기. 그러면 코드가 얼마나 빨리 실행되는지 알 수 있습니까?

아래에는 내가 염려하는 스크립트가 포함되어 있습니다. 그것은 일련의 'a와 b'가 주어진 연습 시험 문제에서 나왔고 당신은 회문을 계산합니다. 따라서 s = "baababa"를 주면 'aa', 'baab', 'aba', 'bab', 'ababa', & 'aba'의 여섯 가지 문장이 있습니다.

def palindrome(s): 
    length = len(s) 
    last = len(s)-1 
    count = 0 

    for index, i in enumerate(s): 
    left=1 
    right=1 
    left2=1 
    right2=1 

    for j in range(0,index+1): #+1 because exclusive 
     if index-left2+1>=0 and index+right2<=last and s[index-left2+1]==s[index+right2]: 
     print s[index-left2+1:index+right2+1] #+1 because exclusive 
     left2 +=1 
     right2 +=1 
     count +=1 

     elif index-left>=0 and index+right<=last and s[index-left] == s[index+right]: 
     print s[index-left:index+right+1] #+1 because exclusive 
     left += 1 
     right +=1 
     count += 1 

    return count

이 O (N) 시간입니까? 전체 목록을 한 번만 반복하지만 더 작은 루프도 있습니다 ...

출처

2013-07-21 natsuki_1996

O (N^2)입니다. 0에서 N까지 하나의 루프가 있고 두 번째 루프는 0에서 i로갑니다. 얼마나 많은 작업을 수행해야하는지 살펴 보겠습니다.

i = 0 | x x _ _ _ _ _ _ - 
i = 1 | x x x _ _ _ _ _ | 
i = 2 | x x x x _ _ _ _ | 
i = 3 | x x x x x _ _ _ N 
i = 4 | x x x x x x _ _ | 
i = 5 | x x x x x x x _ | 
i = 6 | x x x x x x x x _ 
     |-----N + 1-----|

전체 사각형의 영역입니다 ~ N * N (실제로 N : 각 '나는'우리는 0에서 J의 목록의 크기를 보면 내가 + 1의 경우 (하자가 N = 7을) * (N + 1),하지만 여기서는 그다지 중요하지 않습니다.) 그래서 ~ N^2/2 연산이 있음을 알 수 있습니다. 그리고 그것은 O (N^2)입니다.

출처

2013-07-21 18:49:36

죄송합니다, Roman, 그래프가 잘 모르겠습니다. 간단한 설명을 제공해 주시겠습니까? –

대답이 조금 바뀌 었습니다. 충분하지 않다면 나중에 더 자세히 설명하려고합니다. –

감사합니다. 지금 많은 의미가 있습니다! –

글쎄, 이것을 고려해 보자. 입력의 크기는 n = len(s)입니다. 각 문자에 대해 0에서 인덱스로 반복합니다. 그래서 우리는 그 다음 우리는 다음이를 분할하고이를 줄일 수 있습니다 우리에게

for i = 0 to n 
    i^2 + 3i + 2

을 제공

for i = 0 to n 
    (i + 1)(i + 2)

줄일 수있다

for i = 0 to n 
    for j = 0 to i + 1 
     1

다음, 우리가 을 것을 알고 얻을 수 있습니다 3i + 2은 3(n)(n + 1) + 2n = 3n^2 + 5n으로 줄어들며 O (n^2)이므로 곧바로 선형이 아닙니다. 두 번째 for 루프를 사용하여 수행중인 작업을 이해하지 못하면 마지막 문자와 첫 번째 문자를 비교하여 선형 시간에 회문 계산을 수행 할 수 있습니다.

어떻게 궁금해하는 경우 : http://rosettacode.org/wiki/Palindrome_detection#Python

출처

2013-07-21 18:50:05 Ford

감사합니다! 처음에는 복잡했지만 결국 끝내 버렸습니다! –

이는 O (N) 시간이 아니다. enumerate(s) 배열을 한 번만 반복해도됩니다. 매 루프마다 추가 작업을 수행합니다. 배열의 길이가 N이라고 가정합시다. 따라서 총 반복 횟수는 약 1 + 2 + 3 + .. + N이 될 것입니다. N * (N + 1)/2는 O^2) 실행 시간.

출처

2013-07-21 18:53:18

감사합니다! 그 배열은 나에게 의미가 있었다! –

Python Script : O (N) 또는 O (N^2) 시간을 확인하는 방법은 무엇입니까?

답변

관련 문제