분산의 점근 시간은 얼마입니까?

Question

여러분도 알다시피 나는이 모든 런타임 분석을 통해 여전히 꽤 새로운데, 계산하는 각 단계가 올바른지 확인하고 싶습니다. 또한 파이썬 대신 이렇게 의사 코드 형식으로 작성하는 것을 싫어합니다. 여기에 평균에 대한

def mean(n): 
    sum = 0    #cost = 1 
    for i in n:   #cost = n 
     sum += i   #cost = n 
    return sum/len(n)  #cost = 1 

따라서 전체 실행 시간을 간다 = O (1) + O (N) + O (N) + O (1) = O (n)이

(정정 해줘 메신저 잘못된 경우)

def variance(n): 
    var = 0     #cost = 1 
    for i in n:    #cost = n 
     var += (i-mean(n))**2 #cost = n*n or n+n ?? 
    return var/len(n)  #cost = 1 

질문 전체 분산 시간은 어떻게됩니까? 모든 일을 보여줄 수 있습니까? O (N) 작업을 N 번 수행하므로

Answer 1

O (N^2)입니다.

일반적으로 루프는 런타임을 결정할 때 곱셈입니다. 당신의 분산 루프가 "for i in lg (n)"이 되었다면 O (N) operation lg (N) 번 수행 할 것이기 때문에 런타임은 O (N * lg (N))가 될 것입니다. 마찬가지로 다음 런타임 O 것 "나는 N에 대해"내면 조작의 외부 루프와 O (2^N)을하고 있었다 (N *이 2^N)는

다른 일반적인 루프 형식

for(int i = 0; i < N; i++) { 
    for(int j = i; j < N; j++) { 
     // O(1) operation 
    } 
} 

인

여전히 O (N^2)이지만 분석은 조금 까다 롭습니다. arithmetic series "1 + 2 + 3 + ... + n-1 + n"의 합계를 취해야합니다. (n - 1)/2 또는 O (N^2)