이벤트

모집

주제

CSDN 앱 열기.

저작권?CSDN.NET, 1999-2020, 판권 소유

블로그 게시물/게시글/사용자 검색

로그인

Zolade

주의 사항

알고리즘의 시간 복잡성 및 공간 복잡성-

알고리즘의 시간 복잡성 및 공간 복잡성->. 개요 및 혁신

2013-09-20 16:01:26

308 좋아요

조라드

코드 시대 9

닫기

알고리즘의 시간 복잡성과 공간 복잡성 - 개요

일반적으로 주어진 알고리즘에 대해 수행해야 하는 분석은 두 가지가 있습니다. 첫 번째 단계는 알고리즘의 정확성을 수학적으로 증명하는 것입니다. 이 단계에서는 주로 형식적 증명 방법과 순환 불변성 및 수학적 귀납법과 같은 관련 추론 방식을 사용합니다. 알고리즘이 정확하다는 증명을 바탕으로 두 번째 단계는 알고리즘의 시간 복잡성을 분석하는 것입니다. 알고리즘의 시간 복잡도는 입력의 크기가 증가함에 따라 프로그램의 실행 시간이 얼마나 증가하는지를 반영하며, 알고리즘의 강점과 약점을 파악하는 좋은 지표가 될 수 있습니다. 따라서 프로그래머는 기본적인 알고리즘 시간 복잡성 분석을 숙지해야 합니다.

알고리즘의 실행 시간은 알고리즘으로 컴파일된 프로그램을 컴퓨터에서 실행하는 데 소요되는 시간으로 측정해야 합니다. 일반적으로 프로그램의 실행 시간을 측정하는 방법에는 두 가지가 있습니다.

I. 사후 통계 방법

이 방법은 실행 가능하지만 좋은 방법은 아닙니다. 첫째, 설계된 알고리즘의 성능을 평가하려면 먼저 알고리즘에 따라 해당 프로그램을 작성하고 실제로 실행해야하며 둘째, 얻은 시간의 통계는 컴퓨터 하드웨어 및 소프트웨어와 같은 환경 요인에 따라 달라져 알고리즘 자체의 장점이 숨겨지는 경향이 있습니다.

둘째, 사전 분석 및 추정 방법

사후 통계 방법은 컴퓨터 하드웨어 및 소프트웨어와 같은 환경 요인에 더 많이 의존하기 때문에 알고리즘 자체의 장단점을 숨기기가 쉽습니다. 따라서 사람들은 종종 사전 분석 및 추정 방법을 사용합니다.

프로그램을 작성하기 전에 통계적 방법을 기반으로 알고리즘을 추정합니다. 고급 언어로 작성된 프로그램이 컴퓨터에서 실행되는 데 걸리는 시간은 다음 요인에 따라 달라집니다.

(1). 알고리즘이 사용하는 전략과 방법론, (2) 컴파일된 코드의 품질, (3) 문제의 입력 규모, (4) 기계가 명령을 실행하는 속도.

알고리즘은 제어 구조(시퀀스, 분기, 루프)와 기본 연산(내재 데이터 유형에 대한 연산)으로 구성되므로 알고리즘 시간은 이 두 가지의 조합에 따라 달라집니다. 동일한 문제에 대한 여러 알고리즘을 비교하기 위해 연구 중인 문제(또는 알고리즘 유형)의 기본이 되는 기본 연산을 선택하고 해당 기본 연산의 반복 실행 횟수를 알고리즘의 시간 지표로 사용하는 것이 일반적인 관행입니다.

1, 시간 복잡도

(1) 시간 빈도 알고리즘을 실행하는 데 필요한 시간은 이론적으로 계산이 불가능하며 컴퓨터에서 테스트를 실행해야만 알 수 있습니다. 하지만 모든 알고리즘을 컴퓨터에서 테스트할 수도 없고 테스트할 필요도 없습니다. 어떤 알고리즘이 더 많은 시간이 걸리고 어떤 알고리즘이 더 적은 시간이 걸리는지만 알면 됩니다. 그리고 알고리즘이 소요되는 시간은 알고리즘에서 실행되는 명령문의 수에 정비례합니다. 더 많은 문을 실행하는 알고리즘은 더 많은 시간이 걸립니다. 알고리즘에서 실행되는 명령문의 수를 명령문 빈도 또는 시간 빈도라고 합니다. 이를 T(n)으로 표시합니다.

(2) 시간 복잡도 방금 언급한 시간 빈도에서 n은 문제의 크기라고 합니다. n이 계속 변하면 시간 빈도 T(n)도 계속 변합니다. 하지만 때때로 우리는 그것이 변화할 때 어떤 패턴을 보이는지 알고 싶을 때가 있습니다. 그래서 우리는 시간 복잡도라는 개념을 도입합니다. 일반적으로 알고리즘에서 기본 연산의 반복 횟수는 문제 크기 n의 함수이며, T(n)으로 표시됩니다. n이 무한대를 향할 때 T(n)/f(n)의 극한값이 0이 아닌 상수인 보조 함수 f(n)가 있으면 T(n)와 같은 크기의 함수라고 합니다. T(n)=O(f(n))로 설정하는 것을 O(f(n)) 알고리즘의 점근 시간 복잡도 또는 줄여서 시간 복잡도라고 합니다.

또한 위 공식에 사용된 란다우 표기법은 독일의 수 이론가 폴 바흐만이 1892년 저서 '해석수론'에서 소개했고, 또 다른 독일의 수 이론가인 에드먼드 란다우에 의해 대중화되었습니다. 란다우 표기법은 복소함수의 동작을 상한 또는 하한(확실) 경계가 있는 단순 함수의 관점에서 설명하는 데 사용됩니다. 알고리즘의 복잡도를 계산할 때는 일반적으로 큰 O 기호만 사용되며, Landau 표기법의 작은 O 기호, 세타 기호 등은 덜 일반적으로 사용됩니다. 여기서 O는 원래 그리스 대문자였지만 지금은 모두 영어로 대문자화되어 있으며, 작은 O 기호 역시 작은 영어 문자 O를 사용하고, 세타 기호는 그리스 대문자 θ를 유지합니다.

T(n) = ο(f(n f(n))는 n이 양의 무한대를 향할 때 항상 T(n) ≤ C * f(n)이 되도록 하는 상수 C가 있다는 것을 뜻합니다. 간단히 말해, n이 양의 무한대로 향할 때 T(n)은 f(n)만큼 큽니다. 즉, n이 양의 무한대로 향할 때 T (n)의 상한은 C * f(n)입니다. f (n)은 지정되어 있지 않지만 일반적으로 가능한 한 간단한 함수입니다. 예를 들어, O(2 N2+N+1) = O(3n 2+N+3) = O(7 N2+N) = O(n2)이며, 일반적으로 O(N2) 만 사용하면 충분합니다. 큰 O 기호는 상수 c를 숨기고 있으므로 일반적으로 f(n)에는 계수가 없습니다. T(n)을 나무로 생각하면 O(f(n))는 줄기를 나타내며, 다른 모든 세부 사항은 버리고 줄기만 신경을 씁니다.

다른 알고리즘에서 실행되는 명령문의 수가 일정하다면 시간 복잡도는 O(1)입니다. 또한 T(n)=n2+3n+4, T(n)=4n2+2n+1과 같이 주파수가 다른 경우에도 시간 복잡도는 같을 수 있습니다. 주파수는 다르지만 시간 복잡도는 동일합니다. 크기에 따라 일반적인 시간 복잡도는 상수 차수 O(1), 로그 차수 O(log2n), 선형 차수 O(n), 선형 로그 차수 O(nlog2n), 정사각형 차수 O(n2), 입방차수 O(n3), ... , k차 O(nk), 지수차 O(2n) 등이며, 문제 n의 크기가 커질수록 위의 시간 복잡도가 증가하여 알고리즘의 실행 효율이 떨어집니다.

그림을 통해 지수차수 알고리즘보다 다항식차수 O(nk) 알고리즘을 선택해야 한다는 것을 알 수 있습니다.

일반적인 알고리즘의 시간 복잡도는 다음과 같습니다.ο (1)

일반적으로 문제(또는 알고리즘 클래스)의 경우 알고리즘의 시간 복잡도를 논의하기 위해 하나의 기본 연산만 선택하면 됩니다. 때로는 여러 기본 연산을 동시에 고려해야 하는 경우도 있으며, 서로 다른 연산을 수행하는 데 필요한 상대적인 시간을 반영하기 위해 서로 다른 연산에 서로 다른 가중치를 할당할 수도 있습니다. 이를 통해 동일한 문제를 해결하기 위해 완전히 다른 두 알고리즘을 포괄적으로 비교할 수 있습니다.

(3) 알고리즘의 시간 복잡도를 해결하기 위한 구체적인 단계는 다음과 같습니다.

(1) 알고리즘의 기본 문장을 파악합니다.

알고리즘에서 가장 자주 실행되는 문은 기본 문이며, 일반적으로 가장 안쪽 루프에 있는 루프의 본문에 해당합니다.

(2) 기본 문장이 실행되는 횟수의 거듭제곱 계산

기본 문장이 실행되는 횟수의 거듭제곱만 계산하면 되는데, 이는 기본 문장이 실행되는 횟수의 함수에서 가장 높은 거듭제곱만 맞으면 하위 및 상위의 모든 계수를 무시할 수 있다는 의미입니다. 이렇게 하면 알고리즘 분석이 단순해지고 가장 중요한 점인 성장률에 집중할 수 있습니다.

(3) 알고리즘의 시간 성능은 큰 부호로 표시합니다.

기본 명령문이 실행된 횟수의 서수를 큰 ο 부호로 표기합니다.

알고리즘에 중첩 루프가 포함된 경우 기본 문은 일반적으로 가장 안쪽 루프 본문입니다. 알고리즘에 병렬 루프가 포함된 경우 병렬 루프의 시간 복잡도가 증가합니다. 예를 들어:

for(I = 1; I & lt= n; i++)

x++;

for(I = 1; I & lt= n; i++)

for(j = 1; j & lt= n; j++)

x++;

첫 번째 for 루프는 ο(n)의 시간 복잡도를 가집니다. 두 번째 for 루프의 시간 복잡도는 ο (N2)이므로 전체 알고리즘의 시간 복잡도는 ο (n+N2) = ο (N2)입니다.

ο (1)은 기본 문의 실행 횟수가 일정하다는 것을 의미합니다. 일반적으로 알고리즘에 반복문이 없는 한 시간 복잡도는 ο (1)입니다. 여기서 ο (nlog 2n), ο (n), ο (Nlog 2n), ο (N2) 및 ο (n3)을 다항식 시간이라고 하고 ο (2n) 및 ο (n!)을 지수 시간이라고 합니다. 컴퓨터 과학자들은 일반적으로 전자(다항식 시간 복잡도의 알고리즘)를 효율적인 알고리즘으로 간주하고 이러한 문제를 P(다항식) 문제라고 부르며, 후자(지수 시간 복잡도의 알고리즘)를 NP(비결정적 다항식) 문제라고 부릅니다.

일반적으로 다항식 차수 복잡도는 허용되며, 많은 문제에는 다항식 차수 해법, 즉 n 크기의 입력에 대해 n ^ k에서 결과를 얻을 수 있으며, 이를 P 문제라고 합니다. 일부 문제는 더 복잡하고 다항식 시간 해를 갖지 않지만 다항식 시간 내에 추측을 검증할 수 있습니다. 예를 들어 4294967297 는 소수인가요? 바로 시작하려면 4294967297 의 제곱근보다 작은 소수를 모두 구하여 나눌 수 있는지 확인해야 합니다. 오일러는 이 숫자가 641과 6700417의 곱과 같으며 소수가 아니라고 말했는데, 이를 확인하는 것이 좋습니다. 그런데 페르마는 자신의 추측이 옳지 않다는 말을 들었습니다. 큰 수의 인수분해, 해밀턴 고리 등과 같은 문제는 다항식 시간 내에 "해"가 맞는지 검증할 수 있습니다. 이러한 문제를 NP 문제라고 합니다.

(4) 알고리즘의 시간 복잡도를 계산할 때 프로그램을 분석하기 위한 몇 가지 간단한 규칙이 있습니다:

(1). 간단한 입력/출력 문이나 할당 문의 경우, O(1) 시간이 걸리는 것으로 근사화합니다.

(2) 순차 구조의 경우, 일련의 문을 순차적으로 실행하는 데 필요한 시간은 O가 큰 "합산 규칙"이 될 수 있습니다. 일련의 문을 순차적으로 실행하는 데 필요한 시간은 O가 큰 "합산 규칙"이 될 수 있고, 일련의 문을 순차적으로 실행하는 데 필요한 시간은 O가 큰 "합계 규칙"이 될 수 있습니다.

합산 규칙: 두 부분으로 구성된 알고리즘의 시간 복잡도가 T1(n) = O(f(n)), T2(n) = O(g(n))인 경우, t1(n) + t2(n) = o(최대 (f(n), g(n))가 된다는 의미입니다.

특히, t1 (m) = o (f (m)), t2 (n) = o (g (n)) 인 경우, t1 (m) + t2 (n) = o (f (m) + g (n)) 입니다.

(3) if 절과 같은 선택 구조의 경우, 주로 소요되는 시간은 then 또는 else 절을 실행하는 데 걸리는 시간입니다. 조건을 테스트하는 데도 O(1) 시간이 소요된다는 점에 유의하세요.

(4). 루프의 경우 루프 문의 실행 시간은 주로 루프 본문을 실행하고 여러 반복에서 루프 조건을 확인하는 데 소요되는 시간에 반영되며, 이는 큰 O에 대한 "곱셈 규칙"을 사용하여 수행할 수 있습니다.

곱셈 규칙: 두 부분으로 구성된 알고리즘의 시간 복잡도가 T1(n)=O(f(n)), T2(n)=O(g(n))인 경우, T1*T2=O(f(n)*g(n))이 된다는 의미입니다.

(5) 복잡한 알고리즘의 경우 추정하기 쉬운 여러 부분으로 나눈 다음 합계 규칙과 곱셈 규칙을 사용하여 전체 알고리즘의 시간 복잡도를 분석할 수 있습니다.

(1) O(f(n)) + O(g(n)) = O(f(n)), g(n)이 O(f(n))인 경우 (2) O(Cf(n)) = O(f(n)), 여기서 c는 양의 상수입니다.

(5)다음은 몇 가지 일반적인 시간 복잡성의 예입니다.

(1), O(1)

temp = I; I = j; j = 온도;

위 세 가지 단일 문은 빈도 1로 발생합니다. 이 프로그램 세그먼트의 실행 시간은 문제 크기 n에 독립적인 상수입니다. 알고리즘의 시간 복잡성은 일정한 순서이며 T(n) = O(1)로 표시됩니다. O(1). 참고: 알고리즘의 실행 시간이 문제 크기 n에 따라 증가하지 않는다면, 알고리즘에 수천 개의 문이 있더라도 실행 시간은 큰 상수일 뿐입니다. 알고리즘의 시간 복잡도는 O(1)입니다.

(2), 산소(n2)

2.1. I와 j의 내용을 교환합니다.

sum = 0; (한 번)

for(I = 1; I & lt= n; I++) (n+1 번)

for(j = 1; j & lt= n; J++) (n2 번)

sum++; (n2 번)

해결: θ (2n2+n+1) = N2 (θ는 하위 항을 제거한 것이므로 상수 항과 고차 항의 상수 파라미터가 얻어지므로), t(n) = = o(N2);

2.2.

for(I = 1; I & ltn; i++)

{

y = y+1; ①

for(j = 0; j & lt=(2 * n); j++)

x++; ②

}

해법: 문 1은 n-1의 빈도로 발생합니다.

문 2는 (n-1)*(2n+1) = 2 N2-n-1의 빈도로 발생합니다.

f(n) = 2 N2-n-1 + (n-1) = 2 N2-2;

θ (2n2-2) = N2

이 절차의 시간은 다음과 같습니다. 복잡도는 T(n) = O(n2)입니다.

일반적으로 단계적 루프 문은 루프 본문에 있는 문이 실행되는 횟수만 고려하며, 단계 더하기 1, 최종 값 구분, 제어 전달과 같은 문 구성 요소는 무시합니다. 루프 문이 여러 개 있는 경우 알고리즘의 시간 복잡도는 중첩된 레벨 수가 가장 많은 루프 문에서 가장 안쪽에 있는 문의 발생 빈도 f(n)에 의해 결정됩니다.

(3), O(n)

a = 0;

b = 1; ①

for(I = 1; I& lt= n; i++) ②

{

s = a+b; ③

b = a; ④

a = s; ⑤

}

솔루션:문 빈도 1: 2,

문 2의 빈도: n,

문 3의 빈도: n-1,

문 4의 빈도: n-1,

문 5의 빈도: n-1,

t(n) = 2+n+3(n-1) = 4n-1 = O(n).

(4), O(log2n)

I = 1; ①

while(I& lt=n)

I = I * 2; ②

해결: 문 1의 빈도는 1입니다.

문 2의 빈도를 f(n)로 설정하면:2f(n)< = n; f(n)& lt; = log2n

f(n) = log2n의 최대값을 취하고,

T(n) = O(log2n)

(5), O(n3)

for(I = 0; I & ltn; i++)

{

for(j = 0; j & lt I; j++)

{

{

for(k = 0; k & ltj; k++)

x = x+2;

}

}

솔루션:i = m이고 J = K일 때, 내부 루프의 수는 K 입니다. I = M일 때, J는 0, 1, ... , m-1 이므로 여기서 가장 안쪽 루프 * * *는 0 + 1 + ... +M-65438. 그러면 루프 * * *는 O(n3:0+(1-1)* 1/2+... +(n-1)n/2 = n(n+1)(n-65438

(5) 일반적인 알고리즘의 시간 복잡도와 공간 복잡도.

경험 법칙: 여기서 c는 상수이며, 알고리즘의 복잡도가 c, log2n, n, n*log2n이면 알고리즘이 시간 효율이 높고, 2n, 3n, n!이면 n이 약간 클수록 알고리즘이 앞으로 나아가고, 그 중간은 좋지 않습니다.

알고리즘의 시간 복잡성 분석은 매우 중요한 문제입니다. 모든 프로그래머는 그 개념과 기본 방법을 잘 알고 있어야 하며, 그 의미를 정확하게 이해하기 위해 수학적 수준에서 알고리즘의 특성을 탐구하는 데 능숙해야 합니다.

2. 알고리즘의 공간 복잡성.

시간 복잡성에 대한 논의와 유사하게 알고리즘의 공간 복잡성은 알고리즘이 소비하는 저장 공간으로 정의되며 문제 크기 n의 함수이기도 합니다. 점근 공간 복잡성은 일반적으로 공간 복잡성으로 약칭합니다.

공간 복잡성은 알고리즘이 작동하는 동안 일시적으로 차지하는 저장 공간의 양을 측정한 것입니다. 컴퓨터 메모리에서 알고리즘이 차지하는 저장 공간은 알고리즘 자체가 차지하는 저장 공간, 알고리즘의 입력 및 출력 데이터가 차지하는 저장 공간, 알고리즘이 작동하는 동안 일시적으로 차지하는 저장 공간의 세 가지 측면을 포함합니다. 알고리즘의 입력 및 출력 데이터가 차지하는 저장 공간은 풀어야 할 문제에 따라 결정되며, 이는 호출 함수가 매개 변수 목록을 통해 전달하며 이 알고리즘의 차이에 따라 변경되지 않습니다. 저장 알고리즘 자체가 차지하는 저장 공간은 알고리즘 작성 길이에 비례합니다. 이 영역의 저장 공간을 압축하려면 더 짧은 알고리즘을 작성하세요. 알고리즘이 차지하는 임시 저장 공간의 양은 알고리즘마다 다르며, 일부 알고리즘은 문제의 크기에 따라 달라지지 않는 적은 수의 임시 작업 단위만 필요합니다. 이러한 알고리즘을 이 섹션에서 설명하는 알고리즘과 마찬가지로 저장 공간을 절약하는 알고리즘인 "즉시 사용" 알고리즘이라고 부르며, 일부 알고리즘은 문제 n의 크기와 관련된 임시 작업 단위의 수를 차지해야 하고, n이 클수록 더 많은 저장 공간을 차지하며, 9장에서 설명한 빠른 정렬 및 병합 정렬 알고리즘과 같이 모든 알고리즘에서 사용할 수는 없지만 짧은 시간 내에 작성할 수 있는 알고리즘이 있습니다.

예를 들어 알고리즘의 공간 복잡도가 일정할 때, 즉 처리하는 데이터의 양 n의 크기에 따라 변하지 않을 때는 O(1)로 표현할 수 있고, 알고리즘의 공간 복잡도가 2n의 기저의 로그에 비례할 때는 0(10g2n)로 표현할 수 있으며, 알고리즘의 널 I 분할 복잡도가 n에 선형적으로 비례할 때는 0(n)으로 표현할 수 있습니다. 형식 매개변수가 배열인 경우, 실제 매개변수가 전송한 주소에 대한 포인터를 저장하기 위해 하나의 공간, 즉 기계어 길이의 공간만 할당하면 됩니다. 형식 매개변수가 참조되는 경우 해당 실제 매개변수 변수의 주소를 저장하기 위한 공간만 할당하면 됩니다.