algorithm
빅 - 오 (Big-O) 표기법

비고

단순한 루프

다음 함수는 배열에서 최대 요소를 찾습니다.

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

입력 크기는 배열의 크기이며 코드에서 len 이라고 부릅니다.

작업을 세어 봅시다.

int max = INT_MIN;
size_t i = 0;

이 두 과제는 한 번만 수행되므로 두 가지 작업이 있습니다. 반복되는 작업은 다음과 같습니다.

if (max < array[i])
i++;
max = array[i]

루프에 3 개의 연산이 있고 루프가 n 번 수행되면 3n 을 기존의 2 개의 연산에 추가하여 3n + 2 를 얻습니다. 따라서 우리 함수는 3n + 2 연산을 사용하여 최대 값 (복잡도는 3n + 2 )을 찾습니다. 이것은 가장 빠르게 성장하는 항이 n의 인수 인 다항식이므로 O (n)입니다.

당신은 아마도 "작동"이 잘 정의되어 있지 않다는 것을 알았을 것입니다. 예를 들어, if (max < array[i]) 가 하나의 연산 이었지만 아키텍처에 따라이 명령문은 3 개의 명령어 (예 : 하나의 메모리 읽기, 하나의 비교 및 ​​하나의 분기)로 컴파일 될 수 있다고했습니다. 또한 예를 들어 메모리 연산이 다른 연산보다 느리고 캐시 연산에 따라 성능이 크게 달라질지라도 모든 연산을 동일하게 간주했습니다. 또한 return 문, 함수에 대한 프레임이 생성된다는 사실 등을 완전히 무시했습니다. 결국에는 계산을 선택하는 방식에 관계없이 복잡도 분석에는 문제가되지 않으므로 계수 만 변경됩니다 n factor와 상수의 결과는 여전히 O (n)입니다. 복잡성은 알고리즘이 입력 크기에 따라 어떻게 조정되는지 보여 주지만 성능의 유일한 측면은 아닙니다!

중첩 루프

다음 함수는 배열에 각 요소를 취하여 중복이 있는지 확인한 다음 전체 배열을 반복하여 요소가 있는지 확인합니다

_Bool contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len; j++) {
            if (i != j && array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

내부 루프는 각 반복에서 n 과 상수 인 많은 연산을 수행합니다. 바깥 쪽 루프는 몇 가지 상수 연산을 수행하고 안쪽 루프를 n 번 실행합니다. 외부 루프 자체는 n 번 실행됩니다. 따라서 내부 루프 내부의 연산은 n^2 번 실행되고 외부 루프의 연산은 n 번 실행되며 i 대한 할당은 한 번 수행됩니다. 따라서 복잡성은 an^2 + bn + c 와 같을 것이고 가장 높은 항은 n^2 이므로 O 표기는 O(n^2) 입니다.

알고 계시 겠지만 동일한 비교를 여러 번 반복하지 않아도 알고리즘을 개선 할 수 있습니다. 내부 루프에서 i + 1 부터 시작할 수 있습니다. 그 전에 모든 요소가 이미 색인 i + 1 있는 요소를 포함하여 모든 배열 요소에 대해 검사 되었기 때문입니다. 이렇게하면 i == j 검사를 삭제할 수 있습니다.

_Bool faster_contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

분명히이 두 번째 버전은 작업량이 적기 때문에 더 효율적입니다. 그것은 Big-O 표기법으로 어떻게 변환됩니까? 이제 내부 루프 몸체는 1 + 2 + ... + n - 1 = n(n-1)/2 번 실행됩니다. 이것은 여전히 2 차항의 다항식이므로 여전히 O(n^2) 뿐입니다. 복잡성을 분명하게 낮추었습니다. 우리가 수행하는 작업의 수를 대략 2로 나눈 값이기는하지만 Big-O에서 정의한 것과 동일한 복잡성 등급 을 유지합니다. 복잡성을 하위 클래스로 낮추려면 연산 수를 n 으로 무한대 가되는 것으로 나누어야합니다.

O (log n) 예제

소개

다음 문제를 고려하십시오.

L 포함하는 정렬 된 목록이며 n 부호 정수 ( n 충분한 크기이다), 예를 들어 [-5, -2, -1, 0, 1, 2, 4] (여기서, n 7의 값을 갖는다). L 이 정수 0을 포함하는 것으로 알려진 경우, 어떻게 인덱스 0을 찾을 수 있습니까?

진부한 접근

가장 먼저 염두에 두어야 할 것은 0이 발견 될 때까지 모든 색인을 읽는 것입니다. 최악의 경우 연산 수는 n 이므로 복잡도는 O (n)입니다.

이것은 n 작은 값에 대해서는 문제가 없지만보다 효율적인 방법이 있습니까?

이분법

다음 알고리즘을 고려하십시오 (Python3).

a = 0
b = n-1
while True:
  h = (a+b)//2 ## // is the integer division, so h is an integer
  if L[h] == 0:
    return h
  elif L[h] > 0:
    b = h
  elif L[h] < 0:
    a = h

a 와 b 는 0을 찾을 색인입니다. 루프를 시작할 때마다 a 와 b 사이의 인덱스를 사용하여 검색 할 영역을 좁히는 데 사용합니다.

최악의 경우 a 와 b 가 같을 때까지 기다려야합니다. 하지만 얼마나 많은 작업이 필요합니까? n이 아니라, 우리가 루프에 들어갈 때마다 a 와 b 사이의 거리를 약 2로 나눕니다. 오히려 복잡성은 O (log n)입니다.

설명

참고 : "log"라고 쓰면 이진 대수 또는 logbase 2 ( "log_2"라고 쓰는)를 의미합니다. O (log_2 n) = O (log n) (수학을 할 수 있음)처럼 "log_2"대신 "log"를 사용합니다.

x를 연산 수라고합시다. 우리는 1 = n / (2 ^ x)라는 것을 알고 있습니다.

그래서 2 ^ x = n이면 x = log n

결론

연속적인 분열에 직면 할 때 (2 또는 임의의 수로), 로그의 복잡성을 기억하십시오.

O (log n) 유형의 알고리즘

우리가 크기 n의 문제가 있다고 가정 해 봅시다. 이제 알고리즘의 각 단계 (작성해야 함)에 대해 원래의 문제는 이전 크기의 절반 (n / 2)이됩니다.

그래서 각 단계에서 우리의 문제는 절반이됩니다.

문제 공간이 축소되면 (즉, 완전히 해결 된 경우), 점검 조건을 종료 한 후 더 이상 줄일 수 없습니다 (n은 1과 같습니다).

1. k 번째 단계 또는 작업 수를 말하자.

   문제 - 크기 = 1

2. 그러나 우리는 k 번째 단계에서 우리의 문제 크기가 다음과 같아야 함을 알고 있습니다.

   문제 - 크기 = n / 2 ^k

3. 1 및 2부터 :

   n / ^2k = 1 또는

   n = ^2k

4. 양면에 로그온하십시오.

   log _e n = k log _e 2

   또는

   k = log _e n / log _e 2

5. 수식 로그 사용하기 _x m / log _x n = log _n m

   K는 N = ₂ 인 로그

   또는 간단히 k = log n

이제 알고리즘은 log n까지 최대 실행 가능하므로 시간 복잡성은 다음과 같이 나타납니다.
O (log n)

위의 텍스트를 지원하는 코드의 아주 간단한 예는 다음과 같습니다.

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

그래서 어떤 사람이 n이 256인지를 묻는다면, 루프 (또는 문제의 크기를 절반으로 줄이는 다른 알고리즘)가 얼마나 많은 단계를 거쳐 실행되는지를 쉽게 계산할 수 있습니다.

K = _2는 256 로그

k = log ₂ 2 ⁸ (=> log _a a = 1)

k = 8

비슷한 경우에 대한 또 다른 좋은 예는 이진 검색 알고리즘 입니다.

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}