Big-O 표기법을 아십니까?

이 기사는 Codacy 코드 품질 커뮤니티에서 공유되고 있으며 회원 중 한 명이 작성했습니다. 원본 게시물here을 확인하고 자유롭게 커뮤니티에 가입하세요.

저처럼 알고리즘 관련 강의를 들으셨다면 Big-O 표기법이라는 용어를 들어보셨을 것입니다. 알고리즘을 구현하기 전에 비용을 분석하는 가장 기본적인 도구 중 하나입니다.

Big-O 표기법은 대수적 용어를 사용하여 코드의 복잡성을 설명하지만 오늘은 5가지 일반적인 Big-O를 분석할 때 더 간단한 접근 방식을 사용하겠습니다.

O(1) - 상수 복잡성

입력 데이터 세트 크기에 관계없이 실행하는 데 항상 일정한 시간(또는 공간)이 소요됩니다.

int constantExample(int x, int y) {
     return x + y;
}

O(log(n)) - 로그 복잡도

일반적으로 반복할 때마다 문제 크기가 줄어듭니다.

int logarithmicExample(int n) {
     while (n > 1) {
          n = n / 2;
     }
}

O(n) - 선형 복잡도

입력 크기에 정비례하여 선형적으로 증가합니다.

boolean linearExample(IList elements, int value) {
     foreach (var element in elements) {
          if (element == value) return true;
     }
     return false;
}

O(n2) - 2차 복잡도

입력 크기의 제곱에 정비례합니다.

void quadraticExample(int array[], int size) {
     for (int i = 0; i < size; i++) {
          for (int j = 0; j < size; j++) {
               print(array[i], array[j]);
          }
     }
}

O(2n) - 기하급수적 복잡성

입력 데이터 세트에 추가할 때마다 성장이 두 배가 됩니다. 좋은 예는 피보나치 재귀 함수입니다.

int fibonacci(int number) {
     if (number <= 1) return number;
     return fibonacci(number - 1) + fibonacci(number - 2);
}

💡 Big-O 치트 시트를 원하십니까? Head over here ! 최상의 시나리오, 평균 시나리오 및 최악의 시나리오에서 데이터 구조 및 알고리즘의 복잡성을 찾을 수 있습니다.