시간 복잡도 분석

부족하거나 잘못된 점을 지적하여 바로잡아 주십시오.

카탈로그

1 복잡성을 분석하는 이유

2 대 O 표현

3 시간 복잡도 분석 원칙

3.1 순환 횟수가 가장 많은 코드만 주목

3.2 가산원칙

3.3승법원칙

4 흔히 볼 수 있는 몇 가지 시간 복잡도

4.1 O(1)

4.2 O(logn)、O(nlogn)

4.3 O(m+n)、O(m*n)

본문

1 복잡성을 분석하는 이유

사후 통계법

코드를 한 번 훑어보고 통계, 모니터링을 통해 집행 시간과 공간을 차지하는 방법은 한계가 크다.

1.1 테스트 결과는 테스트 환경에 의존한다.

최근에 많은 학우들이 나에게 컴퓨터를 어떻게 선택하느냐고 묻는다. 나는 먼저 어떤 수요를 물어볼 것이다. (컴퓨터는 무엇에 쓰입니까? 프로그래밍 개발입니까, 아니면 후기 제작입니까, 아니면 게임 또는 추극입니까?)후기 제작에 있어 i7을 선택하는 것이 i5보다 좋고, i7의 렌더링 능력은 실제 측정이 i5보다 강하다.게임에 있어서 i7과 i5는 성능이 많이 발휘되지 않기 때문에 i5 프로세서를 사면 수지가 맞는다.물론 산열과 예산 등도 고려해야 한다.잠깐만요.프로그래밍 테스트 환경의 하드웨어가 다르면 테스트 결과에 큰 영향을 줄 수 있다.

1.2 테스트 결과는 데이터 규모의 영향을 많이 받는다

같은 정렬 알고리즘에 대해 정렬을 기다리는 데이터의 질서가 다르면 정렬의 집행 시간에 큰 차이가 생길 수 있다.만약 테스트 데이터가 매우 작다면 테스트 결과는 실제 반응 알고리즘의 성능을 실현할 수 없을 것이다.

2 대 O 복잡도 표현법

/* 1，2，3，……，n    */
int add(int n)
{
    int sum = 0;
    int i = 1;
    for(; i<=n; i++)
    {
        sum = sum + i;
    }
    return sum;
}

각 행 코드의 실행 시간이 unit 인 것으로 가정합니다.time, T(n)는 이 코드의 실행 시간입니다.T(n) = (2n+2)*unit_time

int fun(int n)
{
    int sum = 0;
    int i = 1;
    int j = 1;
    for(; i<=n; i++)
    {
        for(; j<=n; j++)
        {
            sum = sum + i*j;
        }
    }
    return sum;
}

위 코드의 실행 시간은 다음과 같습니다: T(n) = (2n^2 + 2n +3)*unit_time모든 코드의 실행 시간 T (n) 는 행 코드의 실행 횟수 n과 정비례한다
모두: T(n) = O(f(n))대O시간의 복잡도는 실제적으로 구체적인 코드의 진정한 집행 시간을 나타내는 것이 아니라 코드의 집행 시간이 데이터 규모에 따라 증가하는 변화 추세를 나타내는 것으로 점진적인 시간의 복잡도라고도 부른다.n이 크면 공식 중의 저급, 상량, 계수는 성장 추세를 좌우하지 않기 때문에 무시할 수 있다.
그러므로 상기 두 가지 예의 시간 복잡도는 다음과 같다.'T(n)=O(n)T(n)=O(n^2)

3 시간 복잡도 분석 원칙

3.1 순환 횟수가 가장 많은 코드만 주목

대O는 하나의 변화 추세를 나타내기 때문에 하나의 알고리즘, 코드를 분석할 때 순환 실행 횟수가 가장 많은 부분만 주목하면 된다.

int fun1(int n)
{
    int sum = 0;
    int i = 1;
    for( ; i<=n; i++)
    {
        sum = sum + i;
    }
    return sum;
}

fun1의 총 시간 복잡도는 O(n)이다.

3.2 덧셈 원칙

총 복잡도는 양이 가장 큰 코드의 시간 복잡도와 같다.

int fun2(int n)
{
    int sum1 = 0;
    int p = 1;
    for( ; p<100; p++)
    {
        sum1 = sum1 + p;
    }
    
    int sum2 = 0;
    int q = 1;
    for( ; q<n; q++)
    {
        sum2 = sum2 + q;
    }
    
    int sum3 = 0;
    int i = 1;
    int j = 1;
    for( ; i<=n; i++)
    {
        j = 1;
        for( ; j<=n; j++)
        {
            sum3 = sum3 + i*j;
        }
    }
    
    return sum1+sum2+sum3;
}

1단은 n의 규모와 상관없이 100차례 집행되었다.
두 번째 단락의 코드 시간 복잡도는 O(n)이다.
세 번째 단락의 코드 시간 복잡도는 O(n^2)이다.
이 세 단락의 코드의 시간 복잡도를 종합하여 최대 양의 등급을 취하기 때문에 이 코드의 시간 복잡도는 O(n^2)이다.

3.3 곱셈 원칙

플러그인 코드의 복잡도는 플러그인 내외 코드의 복잡도의 곱셈과 같다.

int fun1(int n)
{
    int ret = 0;
    int i = 1;
    for( ; i<n; i++)
    {
        ret = ret + fun2(i);
    }
    return ret;
}

int fun2(int n)
{
    int sum = 0;
    int i = 1;
    for( ; i<n; i++)
    {
        sum = sum + i;
    }
    return sum;
}

이 코드의 시간 복잡도는 다음과 같다. O(n^2)

4 흔히 볼 수 있는 몇 가지 시간 복잡도

지수 단계: O(2^n)와 곱하기 단계: O(n!)다항식 수준이 아닙니다.
일반적으로 시간의 복잡도를 비다항식 등급으로 하는 알고리즘 문제는 NP 문제(Non-Deterministic Polynomial, 비확정 다항식)가 된다.데이터 규모가 n씩 커지면 NP 문제 알고리즘의 실행 시간은 몇 마디로 늘어나 매우 비효율적이다.

4.1 O(1)

int i = 1;
int j = 2;
int sum = i + j;

4.2 O(logn)、O(nlogn)

/* 1 */
int i = 1;
while( i<=n )
{
    i = i*2;
}

/* 2 */
int i = 1;
while( i<=n )
{
    i = i*3;
}

1 코드의 복잡도는 log2(n)2 코드의 복잡성은 log3(n)대수는 서로 변환할 수 있다. log3(n) = log3(2) * log2(n) 그래서: O(log3(n)) = O(C * log2(n)), 그 중에서 C는 상수이고 우리는 계수 C를 무시한다.
그러므로 대수 단계의 시간 복잡도를 모두 다음과 같이 표시한다log(n)만약 코드의 시간 복잡도log(n)가 n번이면 시간 복잡도nlogn(n)가 된다.

4.3 O(m+n)、O(m*n)

int fun1(int m, int n)
{
    int sum1 = 0;
    int i = 1;
    for( ; i<m; i++)
    {
        sum1 = sum1 + i;
    }
    
    int sum2 = 0;
    int j = 1;
    for( ; j<n; j++)
    {
        sum2 = sum2 + j
    }
    
    return sum1+sum2;
}

이 코드의 시간 복잡도는 O(m+n)이다.
이런 상황에 대해 시간 복잡도는 m, n과 모두 관련이 있기 때문에 가법 원칙은 정확하지 않고 곱셈 원칙은 여전히 정확하다.

본문이 끝나 부족한 점을 바로잡아 주십시오.