빅오 표기법( Big-O Notation )

  • 어떤 함수나 알고리즘이 입력 크기 n에 따라 얼마나 빠르게(또는 얼마나 많은 자원을) 증가하는지를 나타냅니다.
  • 핵심은 “점근적 상한선”: 입력이 매우 커질 때, 가장 큰 항만 고려하여 효율성을 비교합니다.
  • 빅오(O) : 최악의 경우 (가장 많이 사용)
  • 빅Ω (오메가) : 최선의 경우
  • 빅Θ (세타): 평균 혹은 정확한 경우 (상하한 모두 같을 때)
  • 평균은 최상과 최악의 평균값으로 시간복잡도는 최악을 기준으로 “빅오 표기법”으로 판단하여 성능을 예측한다.
  • why? 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다.
  • 알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.

복잡도(Complexity)

  • 문제 해결을 위해 적절한 알고리즘을 결정하기 위해서 각각의 성능을 평가한다.
  • 이때 평가를 위해 복잡도를 척도로 사용한다.
  • 복잡도에는 시간복잡도와 공간 복잡도의 개념이 있으며 동일한 기능을 수행하는 알고리즘의 경우 복잡도가 낮을수록 효율적이다.

공간 복잡도(Space Complexity)

  • 알고리즘이 실행되는 동안 사용하는 메모리 양을 측정하는 개념이다

  • 시간과 공간은 반비례적인 경향이 있음
    -> 알고리즘 설계에서는 종종 시간과 공간 자원을 맞바꾸는(trade-off) 상황이 발생한다.

  • 배열의 크기, 동적 할당 여부, 재귀 함수 등이 영향을 준다

  • 고정 공간과 가변 공간, 가변 공간을 사용할 수 있는 구조가 더 효율적이다

  • 요즘은 공간 복잡도보다 시간 복잡도를 훨씬 중요하게 여긴다
  • why? 기술이 좋아져 하드웨어 성능이 발달해 공간이 넘쳐나 메모리 문제에 대해 예전처럼 신경쓰지 않기 때문이다.
  • 하지만 잘못 구성하게 되면 프로그램이 느려져서 사용자 입장에선 불편하기 때문에 잘 짜야한다.

시간 복잡도(Time Complexity)

  • 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.
  • 알고리즘이 데이터를 처리하는 데 걸리는 시간을 나타내는 개념이다.

시간 복잡도의 종류

  1. O(1) - 상수 시간 (Constant Time)
    • 입력값(N)이 증가해도 실행시간은 동일한 알고리즘, index로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도(기본 연산 수라고 생각)
    • 특징 : 가장 효율적인 시간 복잡도
    • STACK의 PUSH,POP 등..

  2. O(log n) — 로그 시간 (Logarithmic Time)
    • 입력이 커질수록 처리 시간은 느리게 증가함.
    • 특징 : 효율적인 탐색 알고리즘에서 많이 사용됨
    • binary search(이진탐색) 알고리즘, tree 형태 자료구조 탐색

  3. O(n) — 선형 시간 (Linear Time)
    • 입력 크기에 비례해서 시간이 증가함
    • 특징 : 가장 일반적인 복잡도
    • for문

  4. O(n log n) — 로그-선형 시간 (Linearithmic Time)
    • 로그 시간과 선형 시간이 곱해진 형태.
    • 효율적인 정렬 알고리즘에서 자주 나타남.
    • 특징 : 대부분의 비교 기반 정렬 알고리즘의 이론적 하한선
    • 퀵 / 병합 / 힙 정렬

  5. O(n²) — 이차 시간 (Quadratic Time)
    • 입력 크기가 두 배가 되면 연산량은 네 배가 됨.
    • 특징 : 간단한 알고리즘이지만 대규모 입력에는 비효율적
    • 2중 for문, 삽입/거품/선택 정렬

  6. O(2ⁿ) — 지수 시간 (Exponential Time)
    • 입력이 조금만 증가해도 실행 시간이 급격히 폭증
    • 특징 : 매우 비효율적, 작은 입력에서만 사용 가능
    • fibonacci 수열, 순열 탐색, 일부 완전 탐색

  7. 요약
시간 복잡도 설명 예시 알고리즘
O(1) 입력 크기와 무관 인덱스 접근
O(log n) 로그 탐색 이진 탐색
O(n) 선형 순회 배열 순회
O(n log n) 정렬 알고리즘 최적 시간 병합 정렬, 퀵 정렬(평균)
O(n²) 이중 루프 버블 정렬, 삽입 정렬
O(2ⁿ) 지수적 증가 피보나치 재귀, 부분집합 탐색

시간 복잡도 실행 순서

  • 실행 속도 O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)

느낀점

코딩도 잘해야하지만 코딩 테스트를 해보면서 시간안에 안들어갔던 기억들이 난다.
다 이런 시간복잡도 때문에 코딩하는거보단 이런걸 신경쓰면서 해야하는게 더 어려운거 같다.
나중에 다시 한번 더 자세히 알아봐야겠다.