시간 / 공간 복잡 도 분석

1. 개념의 도입 은 한 문제 에 대해 여러 가지 알고리즘 이 있 는데 어떤 방법 이 가장 효과 적 인지 어떻게 평가 합 니까?일반적으로 두 가지 측면 에서 평가한다. 하 나 는 시간 효율, 즉 알고리즘 이 데 이 터 를 처리 할 때 걸 리 는 시간 이 고 시간 복잡 도로 평가한다.다른 하 나 는 공간 효율, 즉 알고리즘 이 필요 로 하 는 저장량 의 크기 를 공간 복잡 도로 표시 하 는 것 이다.일반적으로 시간 효율 이 더 중요 하 다 고 생각한다.2. 시간 복잡 도 는 같은 문 제 를 해결 하 는 알고리즘 에 대해 집행 시간 이 짧 지만 당연히 집행 시간 보다 긴 시간 효율 이 높 아야 한다. 여기 서 우 리 는 알고리즘 집행 시간 에 영향 을 주 는 여러 가지 요 소 를 분석 하여 알고리즘 의 집행 시간 을 추산 한다.일반적으로 알고리즘 에서 문 구 를 실행 하 는 횟수 로 알고리즘 의 시간 복잡 도 3, 공간 복잡 도 알고리즘 의 공간 복잡 도 는 프로그램 이 실 행 될 때 사용 하 는 저장 공간 이 일반적으로 데이터 부분 만 차지 하 는 저장 공간 을 통계 하 는 것 이다.
다음 예 를 들 어 2 분 검색 의 비 재 귀적 실현

int bin_search(int arr[], int key, int left, int right)
{
    while (left <= right)
    {
        int mid = (left&right)+(left^right)>>1;
        if (key > arr[mid])
        {
            left = mid + 1;
        }
        if (key < arr[mid])
        {
            right = mid - 1;
        }
        else
            return mid;
    }
    return -1;
}

2 분 검색 의 실현 메커니즘 은 다음 과 같다. 먼저 찾 아야 할 구간 의 중간 위치 mid = (left + right) / 2 를 확정 한 다음 에 찾 아야 할 요소 key 와 중간 위치 에 있 는 요소 arr [mid] 를 비교 한 결과 다음 과 같은 세 가지 상황 이 있다. (1) key = arr [mid] 는 중간 위치 가 찾 아야 할 위치 임 을 설명 하고 중간 위치 에 있 는 아래 표 mid 로 돌아 가 는 것 이다.(2) key > arr [mid] 는 찾 을 위치 가 후반 부 에 있다 는 것 을 설명 하고 구간 의 왼쪽 아래 에 left = (left + right) / 2 + 1 을 표시 한 다음 새로운 구간 에서 찾 습 니 다.(3) key < arr [mid] 는 찾기 위 치 를 앞부분 에 설명 하고 구간 의 오른쪽 아래 에 right 를 표시 하여 right = (lef + right) / 2 - 1 을 이동 한 다음 새로운 구간 에서 찾 습 니 다.여기 서 시간 복잡 도 는 while 의 순환 횟수 k 이 고 순환 할 때마다 현재 의 절반 의 숫자 를 제외 합 니 다. 모두 n 개의 숫자 가 있다 면 우 리 는 이러한 공식 2 ^ k = n 은 k = log2n 을 얻 을 수 있 기 때문에 시간 복잡 도 는 0 (log2n) 입 니 다.공간 복잡 도 는 0 (1) 이다.
피 보 나치 수열 의 비 귀속 실현

 int Fib(int n)
{
    if (n < 2)
        return n;
    int pre = 0;
    int cur = 1;
    int next;
    for (int i = 2; i <= n; i++)
    {
        next = cur + pre;
        pre = cur;
        cur = next;
    }
    return next;
}

상기 코드 에서 for 순환 은 n - 1 회 실행 되 었 기 때문에 이 알고리즘 의 시간 복잡 도 는 0 (n) 이다.공간 복잡 도 는 0 (1) 이다.4. 재 귀 알고리즘 의 시 / 공간 복잡 도 1. 재 귀 알고리즘 의 시간 복잡 도 는 재 귀 총 횟수 매번 재 귀 수 * 2. 재 귀 알고리즘 의 공간 복잡 도 는 대상 의 개수 이다.
다음은 피 보 나치 수열 의 귀환 실현

 int Fib(int n)
{
    if (n < 2)
        return n;
    return Fib(n - 1) + Fib(n - 2);
}

 int Fib(int n)//   
 {
     return n < 2 ? n : Fib(n - 1) + Fib(n - 2);
 }

상기 재 귀 알고리즘 에서 재 귀 의 총 횟수 는 2 ^ n 회 이 고 매번 재 귀 하 는 횟수 는 상수 이 므 로 시간 복잡 도 는 0 (2 ^ n) 입 니 다.최대 n 개의 공간 을 차지 하기 때문에 공간의 복잡 도 는 0 (n) 이다.