[algorithm] 빅 오, 어떻게 계산 / 근사합니까?

나는 여기서 간단한 용어로 설명하기 위해 최선을 다할 것이지만,이 주제는 학생들이 마침내 이해하는 데 몇 달이 걸린다는 경고를받습니다. Java 책 의 데이터 구조 및 알고리즘 의 2 장에 대한 자세한 정보를 찾을 수 있습니다 .

BigOh를 얻는 데 사용할 수있는 기계적 절차 는 없습니다 .

“요리 책”으로서, 코드에서 BigOh 를 얻으려면 먼저 어떤 크기의 입력으로 몇 단계의 계산이 수행되는지 계산하는 수학 공식을 작성하고 있음을 알아야합니다.

코드를 실행할 필요없이 이론적 인 관점에서 알고리즘을 비교하는 것이 목적이 간단합니다. 단계 수가 적을수록 알고리즘이 더 빨라집니다.

예를 들어,이 코드 조각이 있다고 가정 해 봅시다.

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

이 함수는 배열의 모든 요소의 합을 반환하며 해당 함수 의 계산 복잡성 을 계산 하는 수식을 만들려고 합니다.

Number_Of_Steps = f(N)

우리가 그래서 f(N), 함수는 계산 단계의 수를 계산합니다. 함수의 입력은 처리 할 구조의 크기입니다. 이 함수는 다음과 같이 호출됩니다.

Number_Of_Steps = f(data.length)

매개 변수 N는 data.length값을 갖습니다. 이제 함수의 실제 정의가 필요합니다 f(). 이것은 소스 코드에서 이루어지며 흥미로운 각 줄의 번호는 1에서 4까지입니다.

BigOh를 계산하는 방법에는 여러 가지가 있습니다. 이 시점부터 우리는 입력 데이터의 크기에 의존하지 않는 모든 문장이 일정한 C수의 계산 단계 를 취한다고 가정 합니다.

함수의 개별 단계 수를 추가 할 예정이며 지역 변수 선언이나 return 문은 data배열 의 크기에 의존하지 않습니다 .

즉, 1 행과 4 행은 각각 C 단계의 단계를 수행하며 기능은 다음과 같습니다.

f(N) = C + ??? + C

다음 부분은 for문장 의 가치를 정의하는 것 입니다. 우리는 계산 단계의 수를 계산한다는 것을 명심하십시오. 즉, for문장 의 본문 이 실행 N시간을 의미합니다 . C, N시간 을 추가하는 것과 같습니다.

f(N) = C + (C + C + ... + C) + C = C + N * C + C

forget 본문이 몇 번이나 실행 되는지 계산하는 기계적 규칙은 없으므로 코드가 수행하는 작업을 확인하여 계산해야합니다. 계산을 단순화하기 위해 변수 초기화, 조건 및 for명령문의 증분 부분을 무시합니다 .

실제 BigOh를 얻으려면 함수 의 점근 분석 이 필요합니다 . 이것은 대략 다음과 같이 수행됩니다.

1. 모든 상수를 제거하십시오 C.
2. 에서 것은 f()얻가 polynomium 의의를 standard form.
3. 폴리 노뮴의 항을 나누고 성장률에 따라 정렬합니다.
4. N접근 할 때 더 커지는 것을 유지하십시오 infinity.

우리 f()에게는 두 가지 용어가 있습니다.

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

모든 C상수 및 중복 부품을 제거합니다.

f(N) = 1 + N ^ 1

마지막 항은 f()무한대에 도달 할 때 ( 한도를 생각할 때) 커지는 용어이므로 BigOh 인수이며 sum()함수의 BigOh는 다음과 같습니다.

O(N)

까다로운 문제를 해결하기위한 몇 가지 요령 이 있습니다. 가능하면 합계를 사용하십시오 .

예를 들어,이 코드는 요약을 사용하여 쉽게 해결할 수 있습니다.

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

가장 먼저 물어볼 것은의 실행 순서입니다 foo(). 평소에는이어야하지만 O(1)교수에 대해 문의해야합니다. size와 관계 O(1)없이 (거의 대부분) 상수를 의미 C합니다 N.

for문장 번호 하나에 문이 까다 롭습니다. 색인이에서 끝나는 동안 2 * N증분은 2 씩 이루어집니다. 즉, 첫 번째 단계는 단계별로 for실행되므로 N카운트를 2로 나눕니다.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
     = Summation(i from 1 to N)( ... )

문장 번호 두 사람은 그 값에 의존하기 때문에도 까다 롭습니다 i. 살펴보십시오 : 인덱스 i는 0, 2, 4, 6, 8, …, 2 * N 값을 취하고 두 번째 for는 실행됩니다 : N은 첫 번째 것을 N 곱하기 N-2를 두 번째로 N-4 세 번째는 … N / 2 단계까지, 두 번째는 for절대로 실행되지 않습니다.

공식에서 이는 다음을 의미합니다.

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

다시, 우리는 걸음 수를 세고 있습니다. 정의에 따르면 모든 합계는 항상 하나에서 시작하여 하나보다 크거나 같은 수로 끝나야합니다.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(우리는이 가정하는 foo()것입니다 O(1)및 소요 C단계를.)

여기에 문제가 있습니다. i값을 N / 2 + 1위로 가져 가면 내부 Summation은 음수로 끝납니다! 불가능하고 잘못되었습니다. 우리는 총합을 두 부분으로 나눌 필요 i가 N / 2 + 1있습니다.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

중추적 인 순간 이래로 i > N / 2내부 for는 실행되지 않으며 우리는 그 몸체에서 일정한 C 실행 복잡성을 가정합니다.

이제 일부 ID 규칙을 사용하여 요약을 단순화 할 수 있습니다.

1. 합산 (w에서 1에서 N까지) (C) = N * C
2. 합산 (1에서 N까지) (A (+/-) B) = 합산 (1에서 N까지) (A) (+/-) 합산 (1에서 N까지) (B)
3. 합산 (w는 1에서 N까지) (w * C) = C * 합산 (w는 1에서 N) (w) (C는 상수이며, 독립 w)
4. 합산 (w에서 1에서 N까지) (w) = (N * (N + 1)) / 2

대수 적용 :

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 =

   (N / 2 - 1) * (N / 2) / 2 =

   ((N ^ 2 / 4) - (N / 2)) / 2 =

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

그리고 BigOh는 다음과 같습니다.

O(N²)

답변

int array[n];

x = array[0];

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))