Big O, 어떻게 계산 / 근사화합니까?
CS 학위를 가진 대부분의 사람들은 Big O가 무엇을 의미 하는지 확실히 알 것 입니다 . 알고리즘이 실제로 얼마나 (비) 효율적인지 측정하는 데 도움이되며, 해결하려는 문제 가 어떤 범주 에 있는지 알고 있다면 약간의 추가 성능을 끌어낼 수 있는지 파악할 수 있습니다. 1
하지만 어떻게, 궁금 하면 계산이나 알고리즘의 복잡성을 대략?
1 그러나 그들이 말했듯이, 과장하지 마십시오. 조기 최적화는 모든 악의 근원이며 정당한 원인이없는 최적화도 그 이름에 걸 맞습니다.
여기에서는 간단한 용어로 설명하기 위해 최선을 다할 것이지만,이 주제를 학생들이 마침내 이해하는 데 몇 달이 걸린다는 점에 유의하십시오. 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계산 단계를 거친다고 가정 할 것 입니다.
함수의 개별 단계 수를 추가 할 것이며, 지역 변수 선언이나 반환 문은 data배열 의 크기에 의존하지 않습니다 .
즉, 라인 1과 4는 각각 C 단계의 단계를 수행하며 함수는 다음과 같습니다.
f(N) = C + ??? + C
다음 부분은 for문장 의 가치를 정의하는 것 입니다. 계산 단계의 수를 계산하고 있음을 기억하십시오. 이는 for명령문 의 본문 이 실행되는 N시간을 의미합니다 . C, N시간 을 추가하는 것과 같습니다.
f(N) = C + (C + C + ... + C) + C = C + N * C + C
본문 for이 실행되는 횟수를 계산하는 기계적 규칙은 없습니다 . 코드가 수행하는 작업을 확인하여 계산해야합니다. 계산을 단순화하기 위해 for명령문 의 변수 초기화, 조건 및 증가 부분을 무시합니다 .
실제 BigOh를 얻으려면 함수 의 점근 분석 이 필요합니다 . 이것은 대략 다음과 같이 수행됩니다.
- 모든 상수를 제거하십시오
C. - 에서 것은
f()얻가 polynomium 의의를standard form. - 다항식의 항을 나누고 성장률로 정렬합니다.
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)교수님에게 그것에 대해 물어봐야합니다. 크기에 관계 O(1)없이 (거의 대부분) 일정 함을 의미 C합니다 N.
첫 번째 for문장 의 진술은 까다 롭습니다. 색인이에서 끝나는 동안 2 * N2 씩 증가합니다. 즉, 첫 번째 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-2는 두 번째, N-4 세 번째 ... N / 2 단계까지, 두 번째 단계 for는 실행되지 않습니다.
공식에서 이는 다음을 의미합니다.
f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) )
다시, 우리는 단계의 수를 계산 하고 있습니다. 그리고 정의에 따라 모든 합계는 항상 1에서 시작하여 1보다 크거나 같은 숫자에서 끝나야합니다.
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위로 올리면 내부 합산이 음수로 끝납니다! 불가능하고 잘못되었습니다. 우리는 합산을 둘로 나눌 필요 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 규칙을 사용하여 요약을 단순화 할 수 있습니다.
- 합계 (w 1에서 N) (C) = N * C
- 합계 (w 1에서 N) (A (+/-) B) = 합계 (w 1에서 N) (A) (+/-) 합계 (w 1에서 N) (B)
- Summation (w from 1 to N) (w * C) = C * Summation (w from 1 to N) (w) (C is a constant, independent of
w) - 합계 (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²)
Big O는 알고리즘의 시간 복잡도에 대한 상한을 제공합니다. 일반적으로 데이터 세트 (목록) 처리와 함께 사용되지만 다른 곳에서도 사용할 수 있습니다.
C 코드에서 어떻게 사용되는지에 대한 몇 가지 예입니다.
n 개의 요소 배열이 있다고 가정 해 보겠습니다.
int array[n];
배열의 첫 번째 요소에 액세스하려는 경우 배열의 크기는 중요하지 않으므로 O (1)이됩니다. 첫 번째 항목을 가져 오는 데 항상 동일한 시간이 걸립니다.
x = array[0];
목록에서 번호를 찾으려면 :
for(int i = 0; i < n; i++){
if(array[i] == numToFind){ return i; }
}
번호를 찾기 위해 전체 목록을 살펴 봐야하기 때문에 이것은 O (n)입니다. Big-O가 알고리즘의 상한을 설명하기 때문에 첫 번째 시도에서 루프를 한 번 실행해도 Big-O는 여전히 O (n)입니다. .
중첩 루프에 도달하면 :
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
array[j] += 2;
}
}
이것은 O (n ^ 2)입니다. 외부 루프 (O (n))의 각 패스에 대해 전체 목록을 다시 살펴야하므로 n이 곱 해져 n 제곱이됩니다.
이것은 표면을 거의 긁지 않지만 더 복잡한 알고리즘을 분석 할 때 증명과 관련된 복잡한 수학이 작용합니다. 그래도 최소한 기본 사항에 익숙해지기를 바랍니다.
특정 문제에 대한 Big O 시간을 알아내는 방법을 아는 것은 유용하지만, 몇 가지 일반적인 사례를 아는 것은 알고리즘에서 결정을 내리는 데 큰 도움이 될 수 있습니다.
다음은 http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions 에서 가져온 가장 일반적인 경우입니다 .
O (1)-숫자가 짝수인지 홀수인지 결정합니다. 일정한 크기의 조회 테이블 또는 해시 테이블 사용
O (logn)-이진 검색으로 정렬 된 배열에서 항목 찾기
O (n)-정렬되지 않은 목록에서 항목 찾기; 두 개의 n 자리 숫자 더하기
O (n 2 )-간단한 알고리즘으로 두 개의 n 자리 숫자를 곱합니다. 두 개의 nxn 행렬 추가; 버블 정렬 또는 삽입 정렬
O (n 3 )-간단한 알고리즘으로 두 개의 nxn 행렬 곱하기
O (c n )-동적 프로그래밍을 사용하여 출장 세일즈맨 문제에 대한 (정확한) 솔루션 찾기; 무차별 대입을 사용하여 두 개의 논리 문이 동일한 지 확인
O (n!)-무차별 대입 검색을 통해 출장 세일즈맨 문제 해결
O (n n )-점근 복잡도에 대한 더 간단한 공식을 도출하기 위해 O (n!) 대신 자주 사용됩니다.
작은 알림은 다음 big O표기법을 나타 내기 위해 사용되는 점근 (문제의 크기가 무한대로 증가 할 때입니다,), 복잡성을 하고 그것이 일정을 숨 깁니다.
즉, O (n)의 알고리즘과 O (n 2 ) 의 알고리즘 사이 에서 가장 빠른 것이 항상 첫 번째 것은 아닙니다 (항상 n 값이 존재하므로 크기> n의 문제에 대해 첫 번째 알고리즘은 다음과 같습니다. 가장 빠른).
숨겨진 상수는 구현에 따라 크게 달라집니다!
또한 어떤 경우에는 런타임이 입력 크기 n의 결정적 함수가 아닙니다 . 예를 들어 빠른 정렬을 사용하여 정렬합니다. n 요소의 배열을 정렬하는 데 필요한 시간은 상수가 아니지만 배열의 시작 구성에 따라 다릅니다.
다양한 시간 복잡성이 있습니다.
- 최악의 경우 (항상 그다지 의미가있는 것은 아니지만 일반적으로 파악하기 가장 간단 함)
평균 사례 (보통 알아 내기가 훨씬 더 어렵습니다 ...)
...
좋은 소개는 R. Sedgewick과 P. Flajolet 의 An Introduction to the Analysis of Algorithms 입니다.
당신이 말했듯이 premature optimisation is the root of all evil, 그리고 (가능하다면) 프로파일 링 은 코드를 최적화 할 때 항상 사용되어야합니다. 알고리즘의 복잡성을 결정하는 데 도움이 될 수도 있습니다.
여기에서 답을 보면 우리 대부분은 알고리즘을 보고 알고리즘의 순서를 근사화하고 예를 들어 대학에서 생각했던 마스터 방법 으로 계산하는 대신 상식을 사용 한다는 결론을 내릴 수 있다고 생각합니다. 그것으로 나는 교수조차도 우리에게 (나중에) 그것을 계산하는 대신 실제로 생각 하도록 격려했다는 것을 추가해야 합니다.
또한 재귀 함수에 대해 수행되는 방법을 추가하고 싶습니다 .
( scheme code ) 와 같은 함수가 있다고 가정합니다 .
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
주어진 숫자의 계승을 재귀 적으로 계산합니다.
첫 번째 단계는 이 경우 에만 함수 본문에 대한 성능 특성을 시도하고 결정하는 것입니다. 본문에서는 특별한 작업이 수행되지 않고 곱셈 (또는 값 1의 반환) 만 수행됩니다.
따라서 신체 의 성능은 O (1) (상수)입니다.
다음 으로 재귀 호출 의 수를 결정하십시오 . 이 경우 n-1 개의 재귀 호출이 있습니다.
따라서 재귀 호출 의 성능은 다음과 같습니다. O (n-1) (중요한 부분을 버리기 때문에 순서는 n입니다).
그런 다음이 두 가지를 합치면 전체 재귀 함수에 대한 성능을 얻을 수 있습니다.
1 * (n-1) = O (n)
Peter , 제기 된 문제 에 답하기 위해; 여기서 설명하는 방법은 실제로 이것을 아주 잘 처리합니다. 그러나 이것은 여전히 근사치 이며 완전한 수학적으로 정확한 답이 아님 을 명심 하십시오. 여기에 설명 된 방법은 또한 우리가 대학에서 배운 방법 중 하나이며, 올바르게 기억한다면이 예제에서 사용한 계승 알고리즘보다 훨씬 더 고급 알고리즘에 사용되었습니다.
물론 모든 것은 함수 본문의 실행 시간과 재귀 호출 수를 얼마나 잘 추정 할 수 있는지에 달려 있지만 다른 메서드에서도 마찬가지입니다.
비용이 다항식이면 승수없이 최상위 항만 유지하십시오. 예 :
O ((n / 2 + 1) * (n / 2)) = O (n 2 / 4 + n / 2) = O (n 2 / 4) = O (n 2 )
이것은 무한 시리즈에서는 작동하지 않습니다. 일반적인 경우에 대한 단일 방법은 없지만 일부 일반적인 경우에는 다음과 같은 부등식이 적용됩니다.
O (log N ) <O ( N ) <O ( N log N ) <O ( N 2 ) <O ( N k ) <O (e n ) <O ( n !)
정보의 관점에서 생각합니다. 모든 문제는 특정 비트 수를 학습하는 것으로 구성됩니다.
기본 도구는 결정 지점과 엔트로피의 개념입니다. 결정 포인트의 엔트로피는 그것이 당신에게 줄 평균 정보입니다. 예를 들어 프로그램에 두 개의 분기가있는 결정 지점이 포함 된 경우 엔트로피는 각 분기의 확률에 해당 분기 의 역 확률의 로그 2 를 곱한 값입니다. 그것이 당신이 그 결정을 실행함으로써 얼마나 많은 것을 배웠는지입니다.
예를 들어, if두 개의 분기가 있는 문은 둘 다 똑같이 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1의 엔트로피를 갖습니다. = 1. 엔트로피는 1 비트입니다.
N = 1024와 같은 N 개 항목의 테이블을 검색한다고 가정합니다. log (1024) = 10 비트이므로 10 비트 문제입니다. 따라서 결과가 동일 할 가능성이있는 IF 문으로 검색 할 수 있다면 10 가지 결정을 내려야합니다.
이것이 이진 검색으로 얻는 것입니다.
선형 검색을 수행한다고 가정하십시오. 첫 번째 요소를보고 원하는 요소인지 물어 봅니다. 확률은 1/1024이고 그렇지 않은 경우 1023/1024입니다. 그 결정의 엔트로피는 1 / 1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * 약 0 = 약 .01 비트입니다. 당신은 거의 배웠습니다! 두 번째 결정은 그다지 좋지 않습니다. 이것이 선형 검색이 너무 느린 이유입니다. 사실 그것은 당신이 배워야 할 비트의 수에서 기하 급수적입니다.
인덱싱을하고 있다고 가정합니다. 테이블이 많은 빈으로 미리 정렬되어 있고 키의 모든 비트 중 일부를 사용하여 테이블 항목에 직접 인덱싱한다고 가정합니다. 1024 개의 Bin이있는 경우 모든 1024 개의 가능한 결과에 대해 엔트로피는 1/1024 * log (1024) + 1/1024 * log (1024) + ...입니다. 이것은 1/1024 * 10 x 1024 결과 또는 해당 인덱싱 작업에 대한 10 비트 엔트로피입니다. 이것이 인덱싱 검색이 빠른 이유입니다.
이제 정렬에 대해 생각해보십시오. N 개의 항목이 있고 목록이 있습니다. 각 항목에 대해 항목이 목록에서 어디에 있는지 검색 한 다음 목록에 추가해야합니다. 따라서 정렬에는 기본 검색 단계 수의 약 N 배가 필요합니다.
따라서 대략적으로 동일한 결과를 갖는 이진 결정에 기반한 정렬은 모두 약 O (N log N) 단계를 수행합니다. 인덱싱 검색을 기반으로하는 경우 O (N) 정렬 알고리즘이 가능합니다.
거의 모든 알고리즘 성능 문제를 이런 방식으로 볼 수 있음을 발견했습니다.
처음부터 시작하겠습니다.
우선, 데이터에 대한 특정 간단한 작업이 O(1)시간 내에, 즉 입력 크기와 무관 한 시간 내에 수행 될 수 있다는 원칙을 받아들 입니다. C의 이러한 기본 연산은 다음으로 구성됩니다.
- 산술 연산 (예 : + 또는 %).
- 논리 연산 (예 : &&).
- 비교 연산 (예 : <=).
- 작업에 액세스하는 구조 (예 : A [i]와 같은 배열 인덱싱 또는-> 연산자를 따르는 포인터).
- 값을 변수에 복사하는 것과 같은 간단한 할당.
- 라이브러리 함수 호출 (예 : scanf, printf).
이 원리에 대한 정당화에는 일반적인 컴퓨터의 기계 지침 (기본 단계)에 대한 자세한 연구가 필요합니다. 설명 된 각 작업은 적은 수의 기계 명령으로 수행 할 수 있습니다. 종종 한두 가지 지침 만 필요합니다. 결과적으로 C의 여러 종류의 명령문은 O(1)시간 에 따라 실행될 수 있습니다 . 즉, 입력과 관계없이 일정한 시간에 실행됩니다 . 이러한 간단한 포함
- 식에 함수 호출을 포함하지 않는 할당 문.
- 진술을 읽으십시오.
- 인수를 평가하기 위해 함수 호출이 필요하지 않은 문을 작성합니다.
- jump 문은 break, continue, goto, return expression, 여기서 expression은 함수 호출을 포함하지 않습니다.
C에서는 인덱스 변수를 어떤 값으로 초기화하고 루프를 돌 때마다 해당 변수를 1 씩 증가시킴으로써 많은 for 루프가 형성됩니다. for 루프는 인덱스가 제한에 도달하면 종료됩니다. 예를 들어 for-loop
for (i = 0; i < n-1; i++)
{
small = i;
for (j = i+1; j < n; j++)
if (A[j] < A[small])
small = j;
temp = A[small];
A[small] = A[i];
A[i] = temp;
}
인덱스 변수 i를 사용합니다. 루프를 돌 때마다 i를 1 씩 증가시키고 i가 n-1에 도달하면 반복이 중지됩니다.
그러나 지금은 for-loop의 간단한 형태에 초점을 맞 춥니 다. 여기서는 최종 값과 초기 값 의 차이를 인덱스 변수가 증가하는 양으로 나눈 값이 루프를 몇 번이나 돌는지 알려줍니다 . 점프 문을 통해 루프를 종료 할 수있는 방법이없는 한이 수는 정확합니다. 어떤 경우에도 반복 횟수의 상한입니다.
예를 들어 for 루프는를 반복합니다 ((n − 1) − 0)/1 = n − 1 times. 왜냐하면 0은 i의 초기 값이고, n-1은 i가 도달 한 가장 높은 값입니다 (즉, i가 n-1에 도달하면 루프가 중지되고 i = n-에서는 반복이 발생하지 않습니다.) 1), 1은 루프의 각 반복에서 i에 추가됩니다.
루프 본문에서 보낸 시간이 각 반복에 대해 동일한 가장 간단한 경우, 본문에 대한 big-oh 상한에 루프 주위의 횟수를 곱할 수 있습니다 . 엄밀히 말하면 루프 인덱스를 초기화하는 데 O (1) 시간을 추가하고 루프를 돌아 다니는 것보다 한 번 더 테스트하기 때문에 루프 인덱스와 limit의 첫 번째 비교를 위해 O (1) 시간을 추가해야합니다. 그러나 루프를 0 번 실행할 수없는 경우 루프를 초기화하고 한도를 테스트하는 시간은 합산 규칙에 의해 삭제 될 수있는 하위 항입니다.
이제 다음 예를 고려하십시오.
(1) for (j = 0; j < n; j++)
(2) A[i][j] = 0;
우리는 라인 (1)에 시간이 걸린다 는 것을 알고 O(1)있습니다. 분명히 우리는 (1) 행에서 발견 된 상한에서 하한을 뺀 다음 1을 더하여 결정할 수있는 것처럼 루프를 n 번 돌아 다닌다. 본문, 라인 (2)는 O (1) 시간이 걸리기 때문에, j를 증가시키는 시간과 j를 n과 비교하는 시간을 무시할 수 있습니다. 둘 다 O (1)입니다. 따라서, 라인 (1)과 (2)의 실행 시간은이고 N 및 O (1)의 제품 이다 O(n).
마찬가지로, 라인 (2)에서 (4)까지 구성된 외부 루프의 실행 시간을 제한 할 수 있습니다.
(2) for (i = 0; i < n; i++)
(3) for (j = 0; j < n; j++)
(4) A[i][j] = 0;
우리는 이미 라인 (3)과 (4)의 루프가 O (n) 시간이 걸린다는 것을 확인했습니다. 따라서 우리는 O (1) 시간을 무시하여 i를 증가시키고 각 반복에서 i <n인지 테스트하여 외부 루프의 각 반복이 O (n) 시간이 걸린다는 결론을 내릴 수 있습니다.
외부 루프의 초기화 i = 0과 조건 i <n의 (n + 1) 번째 테스트는 마찬가지로 O (1) 시간이 걸리며 무시할 수 있습니다. 마지막으로 외부 루프를 n 번 돌면서 각 반복에 대해 O (n) 시간을 사용하여 총 O(n^2)실행 시간을 제공합니다.
더 실용적인 예입니다.
코드를 분석하는 것이 아니라 경험적으로 코드의 순서를 추정하려는 경우 일련의 증가하는 n 값과 코드 시간을 고수 할 수 있습니다. 로그 스케일에 타이밍을 플로팅합니다. 코드가 O (x ^ n)이면 값은 기울기 n의 선에 있어야합니다.
이것은 코드를 연구하는 것보다 몇 가지 장점이 있습니다. 우선, 런타임이 점근 적 순서에 접근하는 범위에 있는지 확인할 수 있습니다. 또한 주문 O (x)라고 생각한 일부 코드는 예를 들어 라이브러리 호출에 소요 된 시간 때문에 실제로 주문 O (x ^ 2)임을 알 수 있습니다.
기본적으로 시간의 90 %를 차지하는 것은 루프를 분석하는 것입니다. 단일, 이중, 삼중 중첩 루프가 있습니까? 당신은 O (n), O (n ^ 2), O (n ^ 3) 실행 시간이 있습니다.
매우 드물게 (예를 들어 .NET BCL 또는 C ++의 STL과 같은 광범위한 기본 라이브러리가있는 플랫폼을 작성하지 않는 한) 루프를 보는 것보다 더 어려운 문제가 발생합니다 (문의 경우 while, goto, 기타...)
Big O 표기법은 작업하기 쉽고 불필요한 합병증과 세부 사항을 숨기므로 유용합니다 (불필요한 정의를 위해). 분할 및 정복 알고리즘의 복잡성을 해결하는 좋은 방법 중 하나는 트리 방법입니다. 중앙값 절차를 사용하는 퀵 정렬 버전이있어서 매번 완벽하게 균형 잡힌 하위 배열로 배열을 분할한다고 가정 해 보겠습니다.
이제 작업하는 모든 배열에 해당하는 트리를 만듭니다. 루트에는 원래 배열이 있고 루트에는 하위 배열 인 두 개의 자식이 있습니다. 아래쪽에 단일 요소 배열이있을 때까지이 작업을 반복합니다.
O (n) 시간에 중앙값을 찾고 O (n) 시간에 배열을 두 부분으로 나눌 수 있으므로 각 노드에서 수행되는 작업은 O (k)이며 여기서 k는 배열의 크기입니다. 트리의 각 레벨은 (최대) 전체 배열을 포함하므로 레벨 당 작업은 O (n)입니다 (하위 배열의 크기는 n이되며 레벨 당 O (k)가 있으므로이를 더할 수 있습니다) . 입력을 반으로 줄일 때마다 트리에는 log (n) 수준 만 있습니다.
따라서 작업량을 O (n * log (n))로 상한 할 수 있습니다.
그러나 Big O는 때때로 무시할 수없는 세부 사항을 숨 깁니다. 다음을 사용하여 피보나치 수열 계산을 고려하십시오.
a=0;
b=1;
for (i = 0; i <n; i++) {
tmp = b;
b = a + b;
a = tmp;
}
그리고 a와 b가 Java의 BigInteger 또는 임의의 큰 수를 처리 할 수있는 것으로 가정하겠습니다. 대부분의 사람들은 이것이 움찔하지 않고 O (n) 알고리즘이라고 말할 것입니다. 그 이유는 for 루프에 n 개의 반복이 있고 O (1)이 루프 쪽에서 작동하기 때문입니다.
그러나 피보나치 수는 크고 n 번째 피보나치 수는 n에서 지수 적이므로 저장하는 것만으로도 n 바이트 정도가됩니다. 큰 정수로 더하기를 수행하려면 O (n) 작업량이 필요합니다. 따라서이 절차에서 수행되는 총 작업량은
1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)
따라서이 알고리즘은 2 차 시간으로 실행됩니다!
일반적으로 덜 유용하다고 생각하지만 완전성을 위해 알고리즘의 복잡성에 대한 하한을 정의하는 Big Omega Ω 과 상한과 하한을 모두 정의 하는 Big Theta Θ도 있습니다.
알고리즘을 big O 표기법을 알고있는 조각으로 나누고 big O 연산자를 통해 결합합니다. 그것이 내가 아는 유일한 방법입니다.
자세한 내용 은 주제에 대한 Wikipedia 페이지 를 확인하십시오 .
내가 사용하는 알고리즘 / 데이터 구조 및 / 또는 반복 중첩에 대한 빠른 분석에 대한 지식. 어려운 점은 라이브러리 함수를 여러 번 호출 할 때입니다. 때때로 함수를 불필요하게 호출하는지 또는 어떤 구현을 사용하고 있는지 확실하지 않을 수 있습니다. 라이브러리 함수에는 문서 또는 IntelliSense 에서 사용할 수있는 Big O 든 다른 메트릭이든 복잡성 / 효율성 측정이 있어야합니다 .
Big O를 "어떻게 계산합니까"에 관해서는 계산 복잡성 이론의 일부입니다 . 일부 (많은) 특수한 경우에는 몇 가지 간단한 휴리스틱 (예 : 중첩 루프에 대한 루프 수 곱하기)이 함께 제공 될 수 있습니다. 당신이 원하는 것은 상한 추정치이고 그것이 너무 비관적이더라도 상관하지 않을 때-아마도 당신의 질문에 관한 것입니다.
알고리즘에 대한 질문에 정말로 답하고 싶다면 이론을 적용하는 것이 가장 좋습니다. 단순한 "최악의 경우"분석 외에도 나는 상각 분석 이 실제로 매우 유용하다는 것을 발견 했습니다.
첫 번째 경우에있어서, 내부 루프가 실행되는 n-i실행의 총 수에 대한 합이다, 그래서 번 i로부터 거 0행 n-1의 (이하 아닌지보다 하부가 동일하기 때문에)가 n-i. 드디어 얻을 n*(n + 1) / 2수 O(n²/2) = O(n²)있습니다.
두 번째 루프의 경우 외부 루프에 대해 i사이 0에 n포함됩니다. 그러면 내부 루프는 j이보다 엄격하게 클 때 실행 n되며 불가능합니다.
마스터 방법 (또는 해당 전문화 중 하나)을 사용하는 것 외에도 알고리즘을 실험적으로 테스트합니다. 이것은 특정 복잡성 등급이 달성되었음을 증명할 수 없지만 수학적 분석이 적절하다는 확신을 줄 수 있습니다. 이러한 안심을 돕기 위해 실험과 함께 코드 검사 도구를 사용하여 모든 사례를 연습하고 있는지 확인합니다.
아주 간단한 예로서 .NET 프레임 워크의 목록 정렬 속도에 대한 온 전성 검사를 원한다고 가정합니다. 다음과 같이 작성한 다음 Excel에서 결과를 분석하여 n * log (n) 곡선을 초과하지 않는지 확인할 수 있습니다.
이 예에서는 비교 횟수를 측정하지만 각 샘플 크기에 필요한 실제 시간을 조사하는 것도 현명합니다. 그러나 그런 다음 알고리즘을 측정하고 테스트 인프라의 아티팩트를 포함하지 않도록 더욱주의해야합니다.
int nCmp = 0;
System.Random rnd = new System.Random();
// measure the time required to sort a list of n integers
void DoTest(int n)
{
List<int> lst = new List<int>(n);
for( int i=0; i<n; i++ )
lst[i] = rnd.Next(0,1000);
// as we sort, keep track of the number of comparisons performed!
nCmp = 0;
lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }
System.Console.Writeline( "{0},{1}", n, nCmp );
}
// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
DoTest(n);
메모리 리소스가 제한되어있는 경우 문제의 원인이 될 수있는 공간 복잡성도 허용하는 것을 잊지 마십시오. 예를 들어, 기본적으로 알고리즘이 차지하는 공간의 양이 코드 내부의 어떤 요인에도 의존하지 않는다고 말하는 방법 인 상수 공간 알고리즘을 원하는 사람을들을 수 있습니다.
때때로 복잡성은 호출 횟수, 루프 실행 빈도, 메모리 할당 빈도 등이이 질문에 답할 수있는 또 다른 부분입니다.
마지막으로 big O는 최악의 경우, 최상의 경우 및 일반적으로 알고리즘이 얼마나 나쁜지를 설명하는 데 사용되는 최악의 경우에 사용될 수 있습니다.
종종 간과되는 것은 알고리즘 의 예상되는 동작입니다. 알고리즘의 Big-O를 변경하지는 않지만 "미숙 한 최적화.. .."문과 관련이 있습니다.
알고리즘의 예상되는 동작은-매우 멍청한-알고리즘이 가장 많이 볼 가능성이있는 데이터에서 작동 할 것으로 예상 할 수있는 속도입니다.
예를 들어 목록에서 값을 검색하는 경우 O (n)이지만 표시되는 대부분의 목록에 값이 미리 있다는 것을 알고 있으면 알고리즘의 일반적인 동작이 더 빠릅니다.
제대로 정리하려면 "입력 공간"의 확률 분포를 설명 할 수 있어야합니다 (목록을 정렬해야하는 경우 해당 목록이 이미 정렬되는 빈도는 얼마나됩니까? 완전히 반전되는 빈도는 얼마나됩니까?). 종종 대부분 정렬됩니까?) 당신이 그것을 아는 것이 항상 실현 가능한 것은 아니지만 때로는 그렇게합니다.
좋은 질문입니다!
면책 조항 :이 답변에는 거짓 진술이 포함되어 있습니다. 아래 설명을 참조하십시오.
Big O를 사용하는 경우 더 나쁜 경우에 대해 이야기하고있는 것입니다 (나중에 의미하는 바에 대해 자세히 설명). 또한 평균 사례에는 대문자 세타가 있고 최상의 사례에는 큰 오메가가 있습니다.
Big O의 멋진 공식 정의를 보려면 이 사이트를 확인하십시오 : https://xlinux.nist.gov/dads/HTML/bigOnotation.html
f (n) = O (g (n))은 양의 상수 c와 k가 있음을 의미합니다. 즉, n ≥ k 모두에 대해 0 ≤ f (n) ≤ cg (n)입니다. c와 k의 값은 함수 f에 대해 고정되어야하며 n에 의존하지 않아야합니다.
자, 이제 "최상의 경우"및 "최악의 경우"복잡성이란 무엇을 의미합니까?
이것은 아마도 예를 통해 가장 명확하게 설명됩니다. 예를 들어, 정렬 된 배열에서 숫자를 찾기 위해 선형 검색을 사용하는 경우 최악의 경우 는 배열의 항목 수만큼 많은 단계를 수행하므로 배열 의 마지막 요소 를 검색 하기로 결정할 때 입니다. 최상의 경우는 우리가 검색 할 때 될 첫 번째 요소 우리가 처음 확인 후 할 것이기 때문이다.
이 모든 형용사 사례의 복잡성 의 요점은 특정 변수의 크기 측면에서 가상 프로그램이 완료 될 때까지 실행되는 시간을 그래프로 표시하는 방법을 찾고 있다는 것입니다. 그러나 많은 알고리즘의 경우 특정 크기의 입력에 대해 단일 시간이 없다고 주장 할 수 있습니다. 이것은 함수의 기본 요구 사항과 모순되며 모든 입력에는 하나 이상의 출력이 있어야합니다. 그래서 알고리즘의 복잡성을 설명하기 위해 여러 함수를 생각해 냈습니다 . 이제 크기 n의 배열을 검색하는 데는 배열에서 찾고있는 항목과 n에 비례하는 방식에 따라 시간이 달라질 수 있지만 최상의 경우, 평균 사례를 사용하여 알고리즘에 대한 유익한 설명을 만들 수 있습니다. 및 최악의 경우 클래스.
죄송합니다. 너무 잘못 작성되어 기술 정보가 부족합니다. 그러나 바라건대 그것은 시간 복잡성 클래스를 생각하기 쉽게 만들 것입니다. 이것에 익숙해지면 프로그램을 파싱하고 데이터 구조에 따라 배열 크기 및 추론에 의존하는 for-loops와 같은 것을 찾는 것이 간단한 문제가됩니다. 어떤 종류의 입력이 사소한 경우를 초래하고 어떤 입력이 발생하는지 최악의 경우.
이 문제를 프로그래밍 방식으로 해결하는 방법을 모르겠지만 사람들이 가장 먼저하는 일은 수행 된 작업 수에서 특정 패턴에 대한 알고리즘을 샘플링하는 것입니다. 예를 들어 4n ^ 2 + 2n + 1에는 2 개의 규칙이 있습니다.
- 용어의 합계가있는 경우 성장률이 가장 높은 용어가 유지되고 다른 용어는 생략됩니다.
- 여러 요소의 곱이있는 경우 상수 요소는 생략됩니다.
f (x)를 단순화하면, 여기서 f (x)는 수행 된 연산 수에 대한 공식입니다 (위에 설명 된 4n ^ 2 + 2n + 1). 여기에서 big-O 값 [O (n ^ 2))을 얻습니다. 케이스]. 그러나 이것은 구현하기 어려울 수있는 프로그램의 라그랑주 보간을 설명해야합니다. 그리고 만약 진짜 big-O 값이 O (2 ^ n)이고 우리가 O (x ^ n)와 같은 것을 가질 수 있다면이 알고리즘은 아마도 프로그래밍이 불가능할 것입니다. 그러나 누군가가 나를 틀렸다고 증명하면 코드를 줘. . . .
코드 A의 경우 외부 루프는 n+1시간 동안 실행 되며 '1'시간은 내가 여전히 요구 사항을 충족하는지 여부를 확인하는 프로세스를 의미합니다. 그리고 내부 루프는 n시간, n-2시간 .... 따라서 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).
코드 B의 경우 내부 루프가 foo ()를 실행하지 않더라도 내부 루프는 외부 루프 실행 시간 (O (n))에 따라 n 번 실행됩니다.
조금 다른 측면에서 Big-O를 설명하고 싶습니다.
Big-O는 프로그램의 복잡성을 비교하는 것입니다. 즉, 입력이 증가 할 때 프로그램이 얼마나 빠르게 성장 하는지를 의미하며 작업을 수행하는 데 소요되는 정확한 시간이 아닙니다.
Big-O 공식에서 IMHO는 더 복잡한 방정식을 사용하지 않는 것이 좋습니다 (다음 그래프의 방정식을 고수 할 수 있습니다.) 그러나 여전히 다른 더 정확한 공식 (예 : 3 ^ n, n ^ 3, .. .) 그러나 그 이상은 때때로 오해의 소지가 있습니다! 가능한 한 간단하게 유지하는 것이 좋습니다.
여기서 우리는 알고리즘에 대한 정확한 공식을 얻고 싶지 않다는 것을 다시 한 번 강조하고 싶습니다. 입력이 증가 할 때만 어떻게 성장하는지 보여주고 그런 의미에서 다른 알고리즘과 비교하려고합니다. 그렇지 않으면 벤치마킹과 같은 다른 방법을 사용하는 것이 좋습니다.
참고 URL : https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it
'Program Tip' 카테고리의 다른 글
| 파이썬 사전에서 'has_key ()'또는 'in'을 사용해야합니까? (0) | 2020.09.28 |
|---|---|
| “git commit”과“git push”의 차이점은 무엇입니까? (0) | 2020.09.28 |
| Maven 프로젝트에 로컬 jar 파일을 추가하는 방법은 무엇입니까? (0) | 2020.09.27 |
| Matplotlib를 사용하여 플롯을 표시하는 대신 이미지 파일에 저장 (0) | 2020.09.27 |
| div에서 절대 위치 요소를 중앙에 배치하는 방법은 무엇입니까? (0) | 2020.09.27 |