데이터 구조 및 알고리즘 - 03-04 복잡도 분석

문서 목록

1. 사후 통계법

2. 분석 예측법 - 시간, 공간 복잡도 분석법

대O시간 복잡도 표현법

시간 복잡도 분석 방법

1. 순환 실행 횟수가 가장 많은 코드만 주목하기;

2. 덧셈 법칙: 전체 시간 복잡도는 양급이 가장 큰 코드의 복잡도와 같다.

3. 곱셈 법칙: 삽입 코드의 복잡도는 삽입 내외 코드의 복잡도의 곱셈과 같다.

4. 몇 가지 흔히 볼 수 있는 시간 복잡도 실례 분석

4.1. O(1)

4.2. O(logn)、O(nlogn)

4.3. O(m+n), O(m*n)

5. 최적, 최악, 평균, 균등 시간 복잡도

5.1 최적 상황 시간 복잡도

5.2 최악 상황 시간 복잡도

5.3 평균 상황 시간 복잡도

5.4 균등 노점 상황 시간 복잡도

데이터 구조와 알고리즘이 해결하는 것은 및 의 문제는 어떻게 코드를 더욱 빨리 운행하고 어떻게 코드를 저장 공간을 더욱 절약하는가이다.매우 중요한 고려 지표는 알고리즘의 집행 효율이다. 분석 방법은 사후 분석과 앞당겨 예측하는 두 가지가 있다. 및 、 .

1. 사후 통계법

즉 코드를 컴퓨터 하드웨어에서 실제적으로 한 번 운행하고 알고리즘의 실행에 실제 걸리는 시간과 차지하는 메모리를 감시하고 통계하는 것이다.이 방법은 정확하지만 다음과 같은 단점이 있다.

테스트 결과는 테스트에 의존하는 소프트 하드웨어 환경;

테스트 결과는 데이터 규모와 복잡도의 영향을 많이 받는다.

실행 알고리즘이 가장 좋은지 확인할 수 없습니다.

따라서 우리는 알고리즘을 구상하고 작성할 때 실제 운행을 하지 않고 알고리즘의 집행 효율을 대략적으로 추산하고 예측할 수 있도록 하는 방법이 필요하다. 이것은 우리가 업무 요구에 부합되고 효율이 높은 알고리즘 프로그램을 작성하도록 지도할 수 있다.

2. 분석 예측법 - 시간, 공간 복잡도 분석법

대O시간 복잡도 표현법

대략적인 예측으로 볼 때, 우리는 매 줄 코드가 실행하는 데 필요한 시간이 모두 같다고 생각할 수 있으며, 단위 시간unit 로 가정할 수 있다time.여기에 두 가지 상황이 있다. 목표 코드는 순환을 포함하지 않는다.대상 코드는 순환을 포함합니다.전자는 매우 간단하다. 한 번 집행하면 끝이고 집행 시간은 고정값이기 때문에 연구할 만한 것이 없다.후자의 경우 비순환 부분 코드의 집행 시간이 고정되어 있기 때문에 목표 코드의 전체적인 집행 시간은 순환체 코드의 집행 시간에 달려 있다. 이것은 순환체 행수와 각 행의 순환 횟수(덧붙인 순환이 나타날 수 있음)로 쉽게 보면 총 n회로 계산된다. 그러면 전체 집행 시간은 n의 함수이고 T(n)로 기록된다.대상 코드의 T(n) n 는 다음과 같습니다.
그 중에서 T(n)는 코드가 실행되는 시간을 나타내고 n은 데이터 규모의 크기(순환 총 횟수)를 나타내며 f(n)는 줄마다 코드가 실행되는 횟수를 총화하고 O는 정비례 관계를 나타낸다.이것이 바로 O 입니다.주의, 대O시간 복잡도는 실제적으로 코드의 진정한 집행 시간을 구체적으로 나타내는 것이 아니라 표시이기 때문에 점근시간 복잡도라고도 부른다. 약칭 시간 복잡도라고 한다.n이 크면 공식 f(n) 중의 、 、 ， , 최대 양의 그 부분만 주목하면 된다.

시간 복잡도 분석 방법

1. 순환 실행 횟수가 가장 많은 코드만 주목한다.
2. 덧셈 법칙: 전체 시간 복잡도는 양급이 가장 큰 부분의 코드의 복잡도와 같다.
만약 T1(n)=O(f(n)), T2(n)=O(g(n)));그러면 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n)))).
3. 곱셈 법칙: 삽입 코드의 복잡도는 삽입 내외 코드의 복잡도의 곱셈과 같다.
만약 T1(n)=O(f(n)), T2(n)=O(g(n)));그러면 T(n)=T1(n)*T2(n)=O(f(n)))*O(g(n)))=O(f(n)*g(n)). : 복잡도 분석은 상술한 공식을 기억할 필요가 없고 사례를 많이 보고 분석을 연습하면 파악할 수 있다.
4. 몇 가지 흔히 볼 수 있는 시간 복잡도 실례 분석
이상은 두 종류로 나눌 수 있는데 그것이 바로 다항식 등급과 비다항식 등급이다.오직 O(2n)와 O(n!)후자에 속하다.비다항식 양급의 시간 복잡도 알고리즘은 데이터 양이 증가함에 따라 알고리즘의 집행 시간이 급격히 증가하기 때문에 이런 알고리즘은 매우 효과가 없다.
4.1. O(1)
알고리즘의 집행 시간을 상수로 나타내는 알고리즘.일반적인 상황에서 알고리즘에 순환, 귀속 등 조작이 존재하지 않는다면 이 알고리즘의 시간 복잡도는 상량급이다.
4.2. O(logn)、O(nlogn)
다음 사례를 통해 O(logn): 순환체 중 i=i*2를 이해할 수 있다.의 실행 횟수는log2n회입니다

 i=1;

 while (i <= n) {

   i = i * 2;

 }

대수의 를 통해 다른 임의의 밑의 대수는 상계수 형식의log2n(Clog2n)으로 변환할 수 있고 상계수는 무시할 수 있기 때문에 임의의 대수의 복잡도 알고리즘은 그 복잡도를 통일적으로logn로 표시할 수 있다.O(nlogn)에 관해서는 시간 복잡도 곱셈 법칙을 통해 알 수 있듯이 O(nlogn)=O(n)*O(logn)는 복잡도가 O(logn)인 코드가 n번 순환하여 실행되었다.흔히 볼 수 있는 병합 정렬, 빠른 정렬의 시간 복잡도는 O(nlogn)이다.
4.3. O(m+n), O(m*n)
두 데이터 규모 의 알고리즘의 복잡도는 위와 같다. ， !
5. 최고, 최악, 평균, 균등 시간 복잡도
5.1 최적 상황 시간 복잡도
5.2 최악의 경우 시간 복잡도
5.3 평균 상황 시간 복잡도
확률 지식을 활용하여 산출한 기대치(가중평균치). : 하나의 복잡도를 사용하면 수요를 충족시킬 수 있는 경우가 많다. 같은 코드 블록이 서로 다른 상황에서 시간 복잡도가 양적 차이가 있을 때만 가장 좋고 최악이며 평균적으로 구분할 수 있다.
5.4 균등 할당 상황 시간 복잡도
특수한 평균 상황 시간 복잡도