증명 시간 복잡성

내가 정수 및 목록에서 D는 정수의 목록이 두 가지 기능의 복잡성을 결정하기 위해 노력하고있어 : 직관적증명 시간 복잡성

def solve(D, list): 
    for element in List: 
     doFunc(element, D, list) 

def doFunc(element, D, list): 
    quantityx = 0 
    if(D > 0): 
    for otherElement in list: 
     if otherElement == element: 
     quantityx += 1 
    return quantityx + (doFunc ((element+1), (D-1), list)) 
    return 0

, 나는 그것이 O (n²)을 가지고 있다고 생각 여기서 n은 목록의 요소 수량이지만 공식적인 방법으로 증명하고 싶습니다.

출처

2014-03-24 FranckN

첫 번째 관찰 : solve은 doFunc이지만 그 반대는 아닙니다. 따라서 solve의 복잡도는 doFunc의 복잡성에 따라 달라 지지만 그 반대의 경우는 아닙니다. 먼저 doFunc의 복잡성을 파악해야합니다.

하자 E는, D의 함수 목록 N 요소의 개수 doFunc 시간 복잡도 수 T(E, D, N). doFunc이 호출 될 때마다 N 루프를 수행 한 다음 E+1, D-1 및 목록을 변경하여 doFunc을 호출합니다. 이를 바탕으로, 우리는 doFunc의 시간 복잡도는 다음과 같은 재귀 식에 의한 것을 알고

여기

T(E, D, N) = aN + b + T(E+1, D-1, N)

, a 및 b 결정해야 할 몇 가지 상수이다.

이제이 재귀 수식에 대한 기본 사례가 필요합니다. 우리의 기본 경우, 우리가 재발하지 않는 유일한 시간은 D <= 0입니다. D이 음수가 아닌 경우, D = 0을 기본 케이스로 사용합니다.

T(E, 0, N) = c

, c가 결정 될 몇 가지 상수는 : 우리는 다음과 같은 추가 요구 사항을 얻는다. 우리는 패턴을 식별 할 수있는 경우 모두 함께이 퍼팅

이

, 우리가 D의 다른 값에 대한 몇 가지 값을 나열하고 볼 수 있습니다

D T(E, D, N) 
0 c 
1 c + b + aN 
2 c + 2b + 2aN 
3 c + 3b + 3aN 
... 
k c + kb + kaN

이를 토대로을, 우리는 몇 가지 상수에 대한 T(E, D, N) = c + Db + aDN 것을 추측 할 수 a, b, c . 이 수식이 기본 사례를 만족하고 재귀 부분도 만족하는지 확인할 수 있습니다 (시도해보십시오). 그러므로 이것이 우리의 기능입니다.

가정 E, D 및 N 모든 무관 자유롭게 변화, doFunc 시간 복잡도는 가장 O(c + Db + aDN) = O(DN)로 렌더링된다.

solve 이후 통화 doFunc 번리스트의 각 요소에 대해, 그 복잡도는 간단 NdoFunc 배의, 즉 O(DN^2)이다.

출처

2014-03-24 17:01:53 Patrick87

증명 시간 복잡성

답변

관련 문제