데이터 구조 노트 시리즈 - 알고리즘 및 알고리즘 시간 복잡 도

알고리즘 정의: 특정한 문 제 를 해결 하 는 절차 에 대한 설명 으로 컴퓨터 에서 명령 의 유한 한 서열 로 나타 나 고 모든 명령 은 하나 이상 의 조작 을 나타 낸다.
알고리즘 의 다섯 가지 기본 특징: 입 출력, 빈곤 성, 확정 성, 타당 성.
1. 입력: 0 개 이상 입력.
2. 출력: 하나 이상.알고리즘 은 반드시 출력 이 있 고 인쇄 출력 일 수도 있 으 며 하나 이상 의 값 을 되 돌려 줄 수도 있 습 니 다.
3. 빈곤 성 이 있다. 모든 절 차 는 받 아들 일 수 있 는 시간 안에 완성 하고 유한 한 절 차 를 실행 한 후에 무한 순환 이 나타 나 지 않 고 자동 으로 끝난다.
4. 확정 성: 알고리즘 의 모든 절 차 는 정확 한 의 미 를 가지 고 이의 성 이 나타 나 지 않 습 니 다.
5. 타당 성: 알고리즘 의 모든 단 계 는 가능 하 다. 즉, 모든 절 차 는 제 한 된 횟수 를 통 해 완성 할 수 있다.
알고리즘 디자인 의 요구: 정확성, 가 독성, 건장 성 (입력 데이터 가 합 법 적 이지 않 을 때 알고리즘 은 이상 하거나 이상 한 결과 가 발생 하 는 것 이 아니 라 관련 처 리 를 할 수 있 습 니 다), 시간 효율 이 높 고 저장량 이 낮 습 니 다.
알고리즘 의 시간 효율:
> > 분기 구조 에 대해 진 위 를 막론하고 실행 횟수 는 일정 하 며 n 의 변화 에 따라 바 뀌 지 않 기 때문에 단순 한 분기 구조 (순환 구조 에 포함 되 지 않 음) 는 시간 복잡 도 는 O (1) 이다.
아래 코드 의 시간 복잡 도 는 O (1) 입 니 다.코드 실행 횟수 는 n 의 크기 와 무관 합 니 다.

int sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf("%d", sum);

> > 알고리즘 의 복잡 도 를 분석 하 는데 관건 은 순환 구조의 운행 상황 을 분석 하 는 것 이다.
아래 코드 의 시간 복잡 도 는 O (n) 입 니 다.순환 체 의 코드 가 n 회 실행 되 기 때문이다.

int i;
for(i = 0; i < n; i++)
{
    printf(i);             /*   n  */
}

다음 코드 의 시간 복잡 도 는 O (logn) 입 니 다.2 를 곱 하면 n, 즉 2 ^ x = n, x = log2n 을 계산 하 는 것 입 니 다.

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

아래 코드 의 시간 복잡 도 는 O (n ^ 2) 입 니 다.내부 순환 의 시간 복잡 도 는 O (n) 이 고 외부 순환 은 내부 순환 을 n 회 더 실행 하 게 하기 때문에 전체 코드 의 시간 복잡 도 는 O (n ^ 2) 이다.

int i,j;
for(i = 0; i < n; i++)
{
    for(j = 0; j < n, j++)
    {
        printf(j);
    }
}

아래 코드 의 시간 복잡 도 역시 O (n ^ 2) 입 니 다.i = 0 시, 내부 순환 은 n 회, i = 1 시, 내부 순환 은 n - 1 회, i = n - 1 시, 내부 순환 은 1 회 실 행 했 기 때문에 전체 실행 횟수 는 n + (n - 1) + (n - 2) +... + 1 = 0.5n ^ 2 + 0.5n 으로 O (n ^ 2) 를 얻 었 습 니 다.

int i, j;
for(i = 0; i < n; i++)
{
    for(j = i; j < n; j++)    /*     j = i */
    {
        printf(j);
    }
}

흔히 볼 수 있 는 시간 복잡 도 표
실행 횟수 함수
계단.
비공 식 용어
12
O(1)
상수 단계
2n+3
O(n)
선형 단계
3n^2+2n+1
O(n^2)
평방 급
5log2n+20
O(logn)
대수 단계
2n+3nlog2n+19
O(nlogn)
nlog 단계
6n^3+2n^2+3n+4
O(n^3)
입방 계
2^n
O(2^n)
지수 단계
자주 사용 하 는 시간 복잡 도 에 걸 리 는 시간 은 어 릴 때 부터 크게 다음 과 같다.
O(1)n)n)nlogn)n^2)n^3)n)n!)n^n)