빅 오 표기법

빅 오 표기법(Big O notation)은 함수의 증감 추세를 나타내는 점근 표기법의 하나로, 주로 컴퓨터 과학에서 알고리즘의 효율성을 분석할 때 사용한다. 입력 데이터의 크기가 커짐에 따라 알고리즘의 실행 시간이나 공간 요구 사항이 어떻게 변하는지를 수학적으로 기술하며, 특히 최악의 경우에 대한 성능 상한을 나타내는 데 활용된다.

배너 광고

개요

빅 오 표기법은 알고리즘의 성능을 대략적으로 분석하기 위해 사용한다. 입력 크기 $n$ 이 무한히 커질 때 실행 시간이 어떻게 변화하는지를 평가하는 것이 주요 목적이다. 이 표기법은 정확한 연산 횟수보다는 데이터 증가에 따른 성능 변화의 추이를 파악하는 데 중점을 둔다.

입력 크기에 따른 빅 오 표기법의 시간 복잡도 그래프 — 입력 크기 n의 증가에 따른 주요 시간 복잡도 함수들의 증가 추세빅오 표기법(Big O notation)을 알아보자 - WORLD IS WIDE

역사적 배경

독일의 수학자 파울 바흐만과 에드문트 란다우가 발명한 '바흐만-란다우 표기법'의 일종이다. 문자 'O'는 근삿값의 순서를 의미하는 독일어 단어 'Ordnung'에서 따왔다. 수학에서는 수론적 함수의 증가 경계를 표현하거나 멱급수의 오차를 제한하는 데 사용하며, 컴퓨터 과학에서는 알고리즘의 효율성을 분류하는 표준적인 방법으로 자리 잡았다.

입력 크기에 따른 시간 복잡도 그래프 — 다양한 빅 오 표기법의 시간 복잡도 증가 추세 비교빅 오 표기법 (Big O notation)

특징

빅 오 표기법은 다음과 같은 원칙에 따라 계산된다.

상수 계수 무시: 알고리즘의 실행 속도에 영향을 주는 미세한 상수 값은 무시한다.
최고차항 고려: 입력 크기가 커질수록 가장 큰 영향을 미치는 최고차항만을 남기고 나머지 항은 생략한다.
최악의 경우 분석: 알고리즘이 실행될 때 발생할 수 있는 가장 오래 걸리는 상황(상한)을 기준으로 성능을 보장한다.

주요 시간 복잡도

자주 사용되는 시간 복잡도의 종류는 다음과 같다.

표기법	명칭	특징 및 예시
$O(1)$	상수 시간	입력 크기와 관계없이 실행 시간이 일정함. 배열 인덱스 조회 등
$O(\log n)$	로그 시간	입력 크기가 증가할 때 실행 시간이 로그 형태로 증가함. 이진 탐색 등
$O(n)$	선형 시간	입력 크기에 비례하여 실행 시간이 증가함. 배열 전체 순회 등
$O(n \log n)$	선형 로그 시간	병합 정렬, 퀵 정렬 등의 효율적인 정렬 알고리즘
$O(n^2)$	이차 시간	입력 크기의 제곱에 비례함. 버블 정렬, 선택 정렬 등
$O(2^n)$	지수 시간	입력 크기가 커질수록 실행 시간이 급격히 증가함

기타 점근 표기법

빅 오 표기법 외에도 알고리즘의 성능을 나타내는 다른 점근 표기법이 존재한다.

빅 오메가( $\Omega$ ) 표기법: 알고리즘 성능의 최선의 경우(하한)를 나타낸다.
빅 세타( $\Theta$ ) 표기법: 상한과 하한을 동시에 나타내며, 알고리즘의 평균적인 성능을 표현할 때 사용한다.

참고 자료

5건

빅오 표기법 - IT 위키빅오 표기법 - IT 위키 ## 익명 사용자 ### 검색 # 빅오 표기법 빅오 표기법(Big-O Notation)은 알고리즘의 시간 복잡도와 공간 복잡도를 분석하는 데 사용되는 수학적 표기법이다. 주어진 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타내며, 최악의 경우 성능을 분석하는 데 주로 사용된다…https://itwiki.kr/w/%EB%B9%85%EC%98%A4_%ED%91%9C%EA%B8%B0%EB%B2%95 [알고리즘] 시간 복잡도와 Big O 표기법 - 한빛+[알고리즘] 시간 복잡도와 Big O 표기법 - 한빛+ 메뉴 바로가기 검색 및 카테고리 바로가기 본문 바로가기 x ### [알고리즘] 시간 복잡도와 Big O 표기법 | 34.7K # ✅ Big O 표기법 알고리즘의 효율에서 가장 중요한 부분은 ‘n이 커질 때 알고리즘의 단계가 얼마만큼 증가하는가’이고, 이것을 잘 나타…https://www.hanbit.co.kr/channel/view.html?cmscode=CMS7965376216 점근 표기법점근 표기법 빅-O 표기법(Big O notation)은 함수의 정의역에 대한 대략적인 크기를 설명하는 수학적 표기법이다. 빅-O는 독일 수학자 파울 바흐만과 에드문트 란다우가 발명하고 다른 사람들이 확장한 일련의 표기법중 하나이며, 이를 통틀어 바흐만-란다우 표기법이라고 한다. 문자 O는 바흐만이 근삿값의 순서를 의미…https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95 빅오 표기법 - Today I Learned빅오 표기법 - Today I Learned 빅오 표기법 | Today I Learned # 빅오 표기법 알고리즘이 얼마나 빠른지 표시하는 방법이다. 알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정한다. 이렇게 하면 입력 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가하는지 알 수 있…https://seonghui.github.io/TIL/docs/algorithm/big-o.html 빅 O 표기법 - 요다위키빅 O 표기법 - 요다위키 ### Search # 빅 O 표기법 Big O notation 예를 들어 빅의 O표기법:f())∈ O(g())){\displaystyle{\color{ 빨간}())}\in Oᆰ(g()))}}이 M을이 존재한다;0{\displaystyle M>0}(예를 들어, M=1{\displaystyle…https://www.yoda.wiki/wiki/Asymptotic_notation