주어진 코드의 복잡도 결정
코드 조각이 주어지면 일반적으로 복잡성을 어떻게 결정할 것입니까?저는 빅 오 질문에 매우 혼란스러워 하고 있습니다.예를 들어, 아주 간단한 질문이 있습니다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
}
}
TA는 이것을 조합과 같은 것으로 설명했습니다.이와 같이 n은 2 = (n(n-1))/2 = n^2 + 0.5를 선택한 후 상수를 제거하여 n^2가 됩니다.테스트 값을 입력하고 시도해 볼 수 있는데 이 조합은 어떻게 들어오는 건가요?
만약 if 진술이 있다면요?복잡성은 어떻게 결정됩니까?
for (int i = 0; i < n; i++) {
if (i % 2 ==0) {
for (int j = i; j < n; j++) { ... }
} else {
for (int j = 0; j < i; j++) { ... }
}
}
그럼 재귀는...
int fib(int a, int b, int n) {
if (n == 3) {
return a + b;
} else {
return fib(b, a+b, n-1);
}
}
일반적으로, 주어진 함수의 복잡도를 결정하는 방법은 없습니다.
경고!문자가 들어오는 벽!
1. 심지어 중단 여부를 아무도 알 수 없는 매우 간단한 알고리즘이 있습니다.
특정 입력이 주어지면 주어진 프로그램이 중단되는지 여부를 결정할 수 있는 알고리즘은 없습니다.계산 복잡도를 계산하는 것은 알고리즘이 정지한다는 것을 증명해야 할 뿐만 아니라 얼마나 빨리 그렇게 하는지 증명해야 하기 때문에 훨씬 더 어려운 문제입니다.
//The Collatz conjecture states that the sequence generated by the following
// algorithm always reaches 1, for any initial positive integer. It has been
// an open problem for 70+ years now.
function col(n){
if (n == 1){
return 0;
}else if (n % 2 == 0){ //even
return 1 + col(n/2);
}else{ //odd
return 1 + col(3*n + 1);
}
}
2. 어떤 알고리즘들은 이상하고 엇박자의 복잡성을 가지고 있습니다.
일반적인 "복잡도 판단 방법"은 이 사람들 때문에 너무 복잡해지기 쉽습니다.
//The Ackermann function. One of the first examples of a non-primitive-recursive algorithm.
function ack(m, n){
if(m == 0){
return n + 1;
}else if( n == 0 ){
return ack(m-1, 1);
}else{
return ack(m-1, ack(m, n-1));
}
}
function f(n){ return ack(n, n); }
//f(1) = 3
//f(2) = 7
//f(3) = 61
//f(4) takes longer then your wildest dreams to terminate.
3. 일부 함수는 매우 간단하지만 많은 종류의 정적 분석 시도를 혼란스럽게 할 것입니다.
//Mc'Carthy's 91 function. Try guessing what it does without
// running it or reading the Wikipedia page ;)
function f91(n){
if(n > 100){
return n - 10;
}else{
return f91(f91(n + 11));
}
}
그렇기는 하지만, 우리는 여전히 사물의 복잡성을 찾을 수 있는 방법이 필요합니다, 그렇죠?루프는 단순하고 일반적인 패턴입니다.첫 번째 예를 들어보겠습니다.
for(i=0; i<N; i++){
for(j=0; j<i; j++){
print something
}
}
각자 이래로print somethingO(1)입니다. 알고리즘의 시간 복잡도는 해당 라인을 몇 번 실행하느냐에 따라 결정됩니다.음, TA가 언급했듯이, 우리는 이 경우의 조합을 살펴봄으로써 이 작업을 수행합니다.내부 루프는 (N + (N-1) + ... + 1)회, 총 (N+1)*N/2회 작동합니다.
상수를 무시하기 때문에 O(N2)을 얻습니다.
이제 좀 더 까다로운 경우에 대해서는 좀 더 수학적인 지식을 얻을 수 있습니다.입력의 크기 N이 주어졌을 때 알고리즘이 실행되는 데 걸리는 시간을 나타내는 값을 가진 함수를 만들어 봅니다.종종 알고리즘 자체에서 직접 이 함수의 재귀적 버전을 구성할 수 있으므로 복잡도를 계산하는 것은 해당 함수에 경계를 두는 문제가 됩니다.이 함수를 재발 함수라고 합니다.
예를 들어,
function fib_like(n){
if(n <= 1){
return 17;
}else{
return 42 + fib_like(n-1) + fib_like(n-2);
}
}
N의 관점에서 러닝 타임은 다음과 같이 주어질 것이라는 것을 쉽게 알 수 있습니다.
T(N) = 1 if (N <= 1)
T(N) = T(N-1) + T(N-2) otherwise
음, T(N)은 그냥 오래된 피보나치 함수입니다.우리는 귀납법을 사용해서 그것에 한계를 둘 수 있습니다.
예를 들어, 모든 N에 대해 T(N) <= 2^n임을 귀납법으로 증명하자 (즉, T(N)은 O(2^n))
- 기본 케이스: n = 0 또는 n = 1
T(0) = 1 <= 1 = 2^0
T(1) = 1 <= 2 = 2^1
- 귀납 케이스(n > 1):
T(N) = T(n-1) + T(n-2)
aplying the inductive hypothesis in T(n-1) and T(n-2)...
T(N) <= 2^(n-1) + 2^(n-2)
so..
T(N) <= 2^(n-1) + 2^(n-1)
<= 2^n
(우리도 하한선을 증명하기 위해 비슷한 작업을 시도할 수 있습니다.)
대부분의 경우 함수의 최종 실행 시간을 잘 알아맞히면 유도 증명으로 재발 문제를 쉽게 해결할 수 있습니다.물론, 이것은 여러분이 먼저 추측할 수 있도록 요구합니다. 오직 많은 연습만이 여러분을 도울 수 있습니다.
그리고 마지막으로, 저는 현재 일반적으로 사용되는 더 어려운 재발 문제에 대한 유일한 규칙인 마스터 정리에 대해 지적하고자 합니다.까다로운 분할과 정복 알고리즘을 처리해야 할 때 사용합니다.
또한, "if case" 예를 들어보면, 저는 속에 if가 없는 두 개의 개별 루프로 속아서 그것을 속여서 나누어 해결할 것입니다.
for (int i = 0; i < n; i++) {
if (i % 2 ==0) {
for (int j = i; j < n; j++) { ... }
} else {
for (int j = 0; j < i; j++) { ... }
}
}
실행 시간이 다음과 같습니다.
for (int i = 0; i < n; i += 2) {
for (int j = i; j < n; j++) { ... }
}
for (int i = 1; i < n; i+=2) {
for (int j = 0; j < i; j++) { ... }
}
그리고 두 부분은 각각 O(N^2)인 총합에 대하여 O(N^2)인 것을 쉽게 알 수 있습니다.
여기서 "if"를 제거하기 위해 좋은 속임수를 썼다는 것을 주목하십시오.Colatz 알고리즘 예제에서 볼 수 있듯이, 그렇게 하는 일반적인 규칙은 없습니다.
일반적으로 알고리즘 복잡도를 결정하는 것은 이론적으로 불가능합니다.
그러나 이를 위한 냉정하고 코드 중심적인 방법 중 하나는 실제로 프로그램 측면에서 직접 생각하는 것입니다.예를 들어,
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
}
}
이제 복잡성을 분석해 보겠습니다. 그러면 안쪽 줄의 실행 횟수를 세는 간단한 카운터를 추가해 보겠습니다.
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
counter++;
}
}
System.out.println 행은 중요하지 않으므로 제거합니다.
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
counter++;
}
}
이제 카운터만 남았으므로 내부 루프를 단순화할 수 있습니다.
int counter = 0;
for (int i = 0; i < n; i++) {
counter += n;
}
... 왜냐하면 우리는 증분이 정확히 n번 실행된다는 것을 알고 있기 때문입니다.이제 카운터가 정확히 n배 증가하는 것을 확인할 수 있습니다. 따라서 이를 다음과 같이 단순화합니다.
int counter = 0;
counter += n * n;
그리고 우리는 (정확한) O(n2) 복잡도로 나타났습니다 :) 코드에 있습니다 :)
이것이 재귀적 피보나치 계산기에서 어떻게 작동하는지 알아보겠습니다.
int fib(int n) {
if (n < 2) return 1;
return fib(n - 1) + fib(n - 2);
}
루틴을 변경하여 실제 Fibonacci 숫자 대신 내부에서 사용한 반복 횟수를 반환합니다.
int fib_count(int n) {
if (n < 2) return 1;
return fib_count(n - 1) + fib_count(n - 2);
}
그것은 여전히 피보나치입니다! :) 이제 우리는 재귀적 피보나치 계산기가 복잡도 O(F(n))임을 알고 있습니다. 여기서 F는 피보나치 수 그 자체입니다.
자, 이제 좀 더 흥미로운 것을 살펴보겠습니다. 단순한(그리고 비효율적인) 합병 유형입니다.
void mergesort(Array a, int from, int to) {
if (from >= to - 1) return;
int m = (from + to) / 2;
/* Recursively sort halves */
mergesort(a, from, m);
mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
}
for (i = from; i < to; i++)
a[i] = b[i - from];
}
실제 결과가 아니라 복잡성에 관심이 있기 때문에 수행된 작업 단위를 실제로 반환하도록 루틴을 변경합니다.
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
count++;
}
for (i = from; i < to; i++) {
count++;
a[i] = b[i - from];
}
return count;
}
그런 다음 실제로 카운트에 영향을 미치지 않는 선을 제거하고 다음을 단순화합니다.
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
count += to - from;
/* Copy the array */
count += to - from;
return count;
}
여전히 단순화:
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
count += (to - from) * 2;
return count;
}
이제 배열을 실제로 사용할 수 있습니다.
int mergesort(int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(from, m);
count += mergesort(m, to);
count += (to - from) * 2;
return count;
}
이제 from과 to의 절대값은 더 이상 중요하지 않고 거리만 중요하다는 것을 알 수 있으므로 이를 다음과 같이 수정합니다.
int mergesort(int d) {
if (d <= 1) return 1;
int count = 0;
count += mergesort(d / 2);
count += mergesort(d / 2);
count += d * 2;
return count;
}
그러면 다음과 같은 결과를 얻을 수 있습니다.
int mergesort(int d) {
if (d <= 1) return 1;
return 2 * mergesort(d / 2) + d * 2;
}
여기 첫 번째 호출은 정렬할 배열의 크기이므로 복잡도 M(x)에 대해 반복됩니다(두 번째 행에서 쉽게 볼 수 있음).
M(x) = 2(M(x/2) + x)
폐쇄형 솔루션을 사용하려면 이 문제를 해결해야 합니다.이 방법은 해 M(x) = x log x를 추측하고 오른쪽을 확인하는 방법으로 가장 쉽게 수행할 수 있습니다.
2 (x/2 log x/2 + x)
= x log x/2 + 2x
= x (log x - log 2 + 2)
= x (log x - C)
그리고 점근적으로 왼쪽과 동등한지 확인합니다.
x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x
이것이 과잉 일반화이긴 하지만, 목록의 길이가 N개 항목인 Big-O를 목록 측면에서 생각해 봅니다.
따라서 목록의 모든 것에 대해 반복되는 for-loop이 있으면 O(N)이 됩니다.코드에서 한 줄이 0(N)입니다.
for (int i = 0; i < n; i++) {
for loop이 다른 for loop 내부에 중첩되어 있는데 목록의 모든 항목을 살펴보아야 하는 목록의 각 항목에 대해 작업을 수행하면 N개 항목에 대해 N번의 작업을 수행하므로 O(N^2)가 됩니다.위의 예제에서는 실제로 다른 for loop을 for loop 안에 내포합니다.따라서 루프에 대해 각각이 0(N)인 것처럼 생각한 다음, 이들이 중첩되므로 이들을 곱하여 총 값 0(N^2)이 됩니다.
반대로 단일 항목에 대해 빠른 작업을 수행하는 경우 O(1)이 됩니다.한 번의 작업만으로 '길이 n의 목록'을 확인할 수 있습니다.이를 문맥상으로 설명하자면, 위의 예제에서는 다음과 같은 작업을 수행합니다.
if (i % 2 ==0)
0(1)입니다.중요한 것은 '만약'이 아니라, 하나의 아이템이 다른 아이템과 같은지 확인하는 것이 하나의 아이템에 대한 빠른 작업이라는 사실입니다.이전과 마찬가지로 if 문은 루프에 대해 외부에 중첩됩니다.그러나 0(1)이므로 모든 것에 '1'을 곱하는 것이므로 전체 함수의 실행 시간에 대한 최종 계산에서 '눈에 띄는' 영향이 없습니다.
로그와 더 복잡한 상황(jori까지 세는 업무와 같은)을 처리하는 경우, 여기서 좀 더 우아한 설명을 소개하고자 합니다.
저는 Big-O 표기법에 두 가지를 사용하는 것을 좋아합니다: 최악의 시나리오인 표준 Big-O와 일반적으로 발생하는 평균 Big-O입니다.또한 Big-O 표기법이 런타임을 입력 수 N의 함수로 근사화하려고 한다는 것을 기억하는 데 도움이 됩니다.
TA는 이것을 조합과 같은 것으로 설명했습니다.이와 같이 n은 2 = (n(n-1))/2 = n^2 + 0.5를 선택한 후 상수를 제거하여 n^2가 됩니다.테스트 값을 입력하고 시도해 볼 수 있는데 이 조합은 어떻게 들어오는 건가요?
말씀드렸듯이, 일반적인 big-O는 최악의 경우입니다.각 행이 실행되는 횟수를 세어 볼 수 있지만, 첫 번째 예만 보고 n의 길이에 걸쳐 두 개의 고리가 있고, 하나는 다른 고리에 박혀 있으므로 n * n이라고 말하는 것이 더 간단합니다. 그 고리들이 차례로 이어지면 n + n이 될 것이고, 2n과 같습니다.근사치이기 때문에 그냥 'n'이라고 하거나 'linear'라고 하는 것입니다.
만약 if 진술이 있다면요?복잡성은 어떻게 결정됩니까?
보통의 경우와 우수한 경우가 제 생각을 정리하는데 많은 도움이 되는 부분입니다.최악의 경우 if를 무시하고 n^2라고 말합니다.예를 들어 평균적인 경우 n에 대한 루프가 있고 n의 부분에 대한 루프가 절반씩 발생합니다.이것은 n * n/x/2를 제공합니다. (x는 n의 어떤 분율이 당신의 내장된 루프에 루프로 연결되든 간에 말입니다.이것은 n^2/(2x)를 제공하므로 n^2는 동일하게 제공됩니다.이것은 근사치이기 때문입니다.
이것이 당신의 질문에 대한 완전한 답이 아니라는 것을 압니다. 하지만 코드의 대략적인 복잡성에 대해 설명하기를 바랍니다.
위의 답변에서 언급했듯이, 모든 코드 조각에 대해 이것을 결정하는 것은 분명히 불가능합니다. 저는 단지 평균적인 경우 Big-O를 사용하는 것에 대한 아이디어를 논의에 추가하고 싶습니다.
첫번째 스니펫의 경우 n번의 연산을 수행하기 때문에 n^2일 뿐입니다. 만약j로 초기화되었습니다.i, 아니면 에 올라갔거나.i, 당신이 올린 설명이 더 적절하겠지만 현재로서는 그렇지 않습니다.
두 번째 토막글의 경우 첫 번째 토막글이 실행되고 두 번째 토막글은 나머지 토막글이 실행되는 시간의 절반을 쉽게 확인할 수 있습니다.그 안에 무엇이 들어있는지에 따라 (그것이 의존적이기를 바랍니다)n), 수식을 재귀적 수식으로 다시 쓸 수 있습니다.
재귀 방정식(세 번째 토막글 포함)은 다음과 같이 쓸 수 있습니다: 세 번째 토막글은 다음과 같이 나타납니다.
T(n) = T(n-1) + 1
우리가 쉽게 볼 수 있는 것은 O(n)입니다.
Big-O는 단지 근사치일 뿐, 알고리즘이 실행되는 데 얼마나 걸리는지는 말하지 않습니다. 단지 입력의 크기가 커질 때 얼마나 더 걸리는지를 말해줄 뿐입니다.
따라서 입력이 크기 N이고 알고리즘이 일정한 복잡도의 식을 O(1) N번 평가하면 알고리즘의 복잡도는 선형 O(N)입니다.표현식이 선형 복잡도를 가지면 알고리즘은 2차 복잡도를 갖습니다: O(N*N).
일부 식은 지수 복잡도(O(N^N) 또는 로그 복잡도(O(log N))를 갖습니다.루프 및 재귀가 있는 알고리즘의 경우 각 루프 및/또는 재귀 수준의 복잡도를 곱합니다.복잡성 측면에서 루프와 재귀는 동등합니다.알고리즘의 여러 단계에서 서로 다른 복잡도를 가지는 알고리즘은 가장 높은 복잡도를 선택하고 나머지는 무시합니다.그리고 마지막으로, 모든 상수 복잡도는 동등한 것으로 간주됩니다. O(5)는 O(1)과 같고, O(5*N)은 O(N)과 같습니다.
언급URL : https://stackoverflow.com/questions/7885628/determining-the-complexities-given-codes
'programing' 카테고리의 다른 글
| Excel/VBA: 단일 셀을 인수로 전달 (0) | 2023.10.18 |
|---|---|
| Oracle sql developer 3.2에서 sql 워크시트 표시 전환 방법 (0) | 2023.10.18 |
| 정의되지 않은 문자열을 빈 문자열로 바꾸는 방법 (0) | 2023.10.18 |
| 상위 항목을 호버링할 때 스타일 하위 요소 (0) | 2023.10.18 |
| SQL Server에서 행 수준 잠금을 강제할 수 있습니까? (0) | 2023.10.18 |