빅오 표기법의 시각적 소개

(samwho.dev)

1P by GN⁺ 3일전 | ★ favorite | 댓글 1개

빅오 표기법은 함수 성능을 입력 크기 변화에 따른 성장 양상으로 표현함
글에서는 대표적으로 상수, 로그, 선형, 제곱 항목의 빅오를 예시와 함께 설명함
자료구조 및 알고리듬에 따라 시간복잡도가 다르며 입력 배열 정렬, 탐색 등에서 차이를 보임
실제 코드 성능 개선을 위해서는 적절한 데이터 구조 선택과 반복문 내 불필요 연산 제거가 핵심임
빅오는 항상 입력과 실행 시간의 관계를 가장 단순화시켜 나타내며, 성능 개선시 코드를 직접 측정하는 것이 중요함

빅오 표기법 개요

빅오 표기법은 시간 측정 대신 입력 크기(n)에 따른 실행 시간의 성장 양상을 설명하는 방법임
함수 실행 시간을 입력 크기에 따라 분류하며 주로 상수(O(1)) , 로그(O(log n)) , 선형(O(n)) , 제곱(O(n²)) 형태가 분석 대상임
이 글은 초심자도 이해할 수 있도록 각 항목의 개념과 시각적 사례, 실제 코드 예시를 통해 설명함

반복(Iterating)과 선형 알고리듬

sum(n) 함수는 1에서 n까지 더하는 반복 구조 예시로, 입력값 n이 커질수록 수행 시간도 정비례로 증가함
실제로 sum(1e9)은 약 1초, sum(2e9)은 약 2초 소요로 벽시계 시간(wall-clock time)이 O(n) 패턴으로 성장함
시간복잡도는 함수 입력과 실행 시간의 관계이며, 이를 빅오 표기법으로 표현함(O(n) — n에 비례)
반복 대신 수학 공식을 활용한 sum(n) = (n*(n+1))/2은 실행 시간이 입력값 n과 무관하게 일정(상수) 함
이런 함수는 상수 시간복잡도 O(1) 라고 하며, 입력값 변화에 따른 실행 시간 성장 없음이 특징임

빅오 표기법 문법

빅오의 O는 “Order(성장 차수)”에서 유래하며, 성장 형태 자체만을 표시
실제 실행 시간의 절대값이 아니라 입력 대비 성장의 '패턴'만을 간결히 표기함
예를 들어 O(n) 함수라도 'O(2n)'이나 'O(n+1)'처럼 복잡하게 적지 않고, 가장 단순한 항만 선택

입력 구성을 이용한 시간 단축

sum(n) 공식 예시처럼 알고리듬 개선을 통해 시간복잡도가 O(n)에서 O(1)로 변환 가능
다만, 상수 시간복잡도라고 무조건 빠른 것은 아니며, 어떤 연산일지에 따라 실행시간 전체는 달라질 수 있음
O(n) 알고리듬이 특정 입력에서는 O(1)보다 빠를 수 있으나, 입력 크기가 커지면 항상 O(1) 방식이 우세해짐

정렬(Sorting)과 제곱(Quadratic) 알고리듬: 버블 정렬 예시

버블 정렬(Bubble Sort) 은 인접 수 교환을 반복하며 배열을 정렬하는 기본 예시임
이미 정렬된 경우는 1회 반복(O(n)), 역순은 반복적으로 n회 순회 필요 → 최악의 경우 전체 연산 수 n²
O(n²) 알고리듬은 입력이 커질수록 실행 시간이 제곱 형태로 크게 증가
실제 활용에서 빅오는 항상 최악의 경우(worst-case) 기준임(단, 경우에 따라 평균/최선도 표기)
배열 초기 상태에 따라 반복 회수가 줄어들기도 하지만, 최악 케이스 고려로 항상 제곱 시간복잡도로 분류

탐색(Searching)과 로그 알고리듬: 이진 탐색 예시

이진 탐색(Binary Search) 은 정렬된 범위의 중앙값을 추정하고, 매 단계마다 후보 영역을 절반씩 소거함
예를 들어 1~100 사이 특정 수 맞추기에 최대 7회, 1~10억까지도 31회 미만 시도로 가능
매 단계마다 후보 리스트가 반씩 줄어드는 구조로 실행 시간은 O(log n) (로그 시간복잡도)임
로그형 알고리듬은 n이 커질 때 증가 속도가 굉장히 느린 형태를 보임(선형 또는 제곱에 비해 월등히 효율적)
그래프 비교 시 log n, n, n²순으로 성장 차이가 극명하게 드러남

실제 적용: 시간복잡도 개선 팁

리스트에서 항목 찾기

기본적으로 배열에서 값을 찾는 함수는 O(n) 에 해당함
빈번하게 탐색하는 경우, Set과 같은 자료구조를 사용하면 O(1) 로 향상 가능
단, new Set(array)로 변환하는 과정 자체가 O(n) 이므로 빈번 조회에만 적절함(변환 비용 고려)
예: items.has("banana")는 상수 시간복잡도를 제공

인덱스 활용 반복문 작성

아래와 같이 반복문 내부에서 .indexOf를 사용하는 코드가 흔히 성능 문제의 원인임

function buildList(items) {
  const output = [];
  for (const item of items) {
    const index = items.indexOf(item);
    output.push(`Item ${index + 1}: ${item}`);
  }
  return output.join("\n");
}

.indexOf는 루프 내에서 O(n) 연산이기 때문에, 전체적으로 O(n^2) 패턴이 됨

인덱스 기반 반복 또는 forEach((item, index) => ...) 활용 시 O(n) 으로 개선됨

function buildList(items) {
  const output = [];
  for (let i = 0; i < items.length; i++) {
    output.push(`Item ${i + 1}: ${items[i]}`);
  }
  return output.join("\n");
}

메모이제이션(Memoization) 활용

팩토리얼과 같이 반복 호출 시 중복 계산되는 구조는 결과 캐싱(Map 활용) 을 적용하여 성능 향상 가능
Map에서의 조회는 O(1) 에 해당하여 불필요 재계산 최소화

단, 캐싱은 평균 시간 개선에 기여하며, 최악 시간복잡도 자체는 변하지 않아도 효율적 성능 향상 가능

const cache = new Map();
function factorial(n) {
  if (cache.has(n)) {
    return cache.get(n);
  }
  if (n === 0) {
    return 1;
  }
  const result = n * factorial(n - 1);
  cache.set(n, result);
  return result;
}

성능 평가와 결론

코드 성능 개선 시 이론상 시간복잡도와 함께 직접 실행 테스트로 실제 개선 여부를 확인해야 함
빅오는 입력과 실행 시간의 관계와 성장 패턴을 가장 본질적으로 단순화해서 표현함
좋은 알고리듬 선택 및 데이터 구조 최적화로 코드 효율성을 극대화할 수 있음

요약 정리

빅오 표기법은 함수 입력값과 실행 시간의 관계를 표현
주요 성능 등급: O(1) (상수), O(log n) (로그), O(n) (선형), O(n^2) (제곱)
효율적 코드 작성 위해서는 적절한 알고리듬과 반복문 최적화가 중요
실제 성능은 직접 측정해 개선 여부를 검증 필요
성장 패턴 비교 그래프를 활용해 시간복잡도 특성을 한눈에 파악 가능

▲

GN⁺ 3일전 [-]

Hacker News 의견

이 글과 HN 댓글들도 Big O Notation을 설명하고 실제 활용과 기술적 세부사항에 대해 논쟁하는 전통을 계속 이어가는 중임. 참고할 만한 예시로 이 해설글과 전문가 태도에 관한 글이 있음
- 저번 글 댓글을 보면 Pyon이라는 유저가 독설적이고 융통성 없는 태도를 보였음. 하지만 Ned의 반박도 썩 훌륭하진 않음. 기술적 세부내용을 정확히 설명하지 않고, 그냥 “특정 세부사항”이라고만 반복해서 돌려 말하는 느낌임. 왜 그의 비판이 단순한 딴지였는지도, 왜 굳이 내용 자체도 배척하는지도 아쉬움. Ned가 온라인에서의 소통과 공감 자체엔 옳은 방향성을 보여주긴 함. 그래도 교육자라면 왜 그 기술적 논점이 너무 세세하거나 딴지인지 한번은 짚어줬으면 좋겠음. Ned 스스로 “수십 년간 몰랐다“고만 하니, 그게 충분하지 않은 느낌임. 그리고 원 댓글 스레드를 다시 보니 실제로 Ned는 꽤 외교적이고 진지하게 논쟁을 했음. 그런데 왜 블로그 글에선 그 분석이 누락됐는지 의문임. 개인적으로 기술적 세부사항이 뭔지는 잘 모르겠는데, 한 번은 간단하게 요약 설명해줬으면 하는 마음임
- 나는 비판적 전문가에 가까움. 블로그에서 복잡한 주제를 가르치려는 시도를 보면 항상 실망하는 이유는, 대개 비전문가가 설명하면서 정확성을 놓친다는 점임. 그 결과 1) 부정확한 내용이 인터넷 여기저기로 복붙되고, 2) 독자들은 블로그 수준만 보고 더 안 배우려 하면서 무지를 강화하게 됨. 그리고 추가로, 페이지 레이아웃도 마음에 안 들었음. ADHD와 기억력이 떨어지는 내 경험상, 적절한 형식(소제목/굵게/구분색/불릿 등)으로 끊어줘야 따라갈 수 있는데, 이 글은 그냥 텍스트 벽처럼 느껴졌음. 요점 파악에 시간이 더 걸릴수록 집중을 잃게 됨. Simple Wikipedia Big O 설명이 훨씬 직설적임. 반면 정식 위키피디아 페이지는 수학이 갑자기 나와서, 직접 보면 Big O가 생각보다 훨씬 복잡한 주제임을 알게 되고 “단순화하는 건 오히려 안 좋을 수도 있겠다”는 결론에 이름
- 두 번째 링크는 Big-O에 관한 이야기가 아니고, 저런 태도를 본받을 필요는 없음
- Ned가 며칠 전에 내게 이메일을 보내줬는데, 기분 좋게 나도 이런 논의에 기여하고 있음
- 이런 글들을 보면 진짜 교훈은 “틀리거나 오해의 소지가 있는 설명이 있으면 교정을 멈추라는 게 아니라, 온라인에서는 일부 ‘전문가’들이 단순히 논쟁에서 이기고자만 한다”는 점임. Pyon의 태도를 보면 상당히 공격적이고 인터넷 트롤 같았음. “그러니까 기술적 세부사항은 중요하지 않고 부정확해도 괜찮다”는 결론을 내려선 절대 안 됨
O(1)이 실제로는 해싱 함수를 이용하는데, 이는 단순하진 않지만 일정한 연산 소요가 발생함. 데이터가 아주 적으면 O(n^2)와 같은 최악의 알고리즘이 오히려 실제 시간 면에서 더 빠를 수 있음
- 맞는 말이지만 너무 크게 떠들진 않는 게 좋음. 실무에서 n^2면 컴퓨터가 멈춘다고 이해시키는 것만도 힘든 법임. 게다가 경우에 따라선 mod처럼 완벽한 해시함수도 쓸 수 있음
Big-O의 현대적 중요성이 예전만 못하다고 느낌. 요즘 하드웨어는 멀티스레드, 파이프라인, NUMA, 복잡한 캐싱 등으로 언제는 한 사이클 미만에도 끝나고 반대로 수백~수천 사이클이 걸리는 연산도 있음. innermost loop 횟수만으로 알고리즘을 설명하려 들면 오히려 현실을 왜곡하게 됨. 그리고 Big-O를 논할 땐 Big-Omega와 같은 다른 표기도 반드시 언급해야 함. (참고로 Big-O를 소재로 한 애니메이션도 재밌게 봤음)
- Big-O 이론은 저런 장치 종속적 요소와 상관없이 연산량을 정의하려고 탄생한 개념임. 그런 의미에서 시대를 타지 않는 도구임. (괜찮은 발표자라면 대개 “C 같은 상수는 N이 작을 땐 매우 중요한 요소가 된다”고 반드시 언급해주기도 함)
진짜 흥미로운 건 양자계산에서 어떤 연산은 원자 수에 대해 O(n^7)로 증가하지만, 과학자들이 실제로 이 계산을 실행하는 걸 두려워하지 않는다는 점임. 왜냐면 N이 충분히 작고, 컴퓨터와 메모리는 계속 빨라지며, 결과값은 엄청난 가치가 있기 때문임. (내가 컴퓨터과학 전문가는 아니라 O() 표기법을 잘못 썼으면 양해 바람)
- 그냥 “n^7에 비례해 증가“라고 하면 됨. O(n^7)라고 하면 대부분 이해는 하는데, O는 수학적으로는 ‘상한’만 나타내므로 엄밀히 정확하진 않음. 정말 정확히 말하려면 Ω(n^7)처럼 쓰는 게 맞음
시각화가 정말 마음에 듦. 예전에 알고리즘 배웠던 입장에서도 시각적으로 보는 경험이 여전히 큰 도움이 됨
전기공학을 수강해서 그런지 Big O Notation이 언제나 뭔가 대충 건너뛰는 개념처럼 다뤄져 왔다고 느낌. 항상 당연히 아는 내용인 것처럼 취급되어서 정말 친절하게 설명하는 경우를 못 본 것 같음. 어느 정도 수준의 수학이나 컴공 과정에서 이 개념이 처음 소개되는지 궁금함
- 전산 전공 코스의 Discrete Math 시간에서 가장 체계적으로 Big-O를 배웠음
- 내 학교에선 Algorithm Analysis(필수과목)에서 Big-O와 여러 증명법을 가르쳤음. 다만 이 과목은 거의 3~4학년때 듣는 코스였고, 실제로는 이미 1학년 정도면 어느 정도 개념을 흡수했을 거라는 암묵적 전제가 있었음(아마도 주변에서 자연스럽게 배운다는 느낌)
- 수학적으로 함수 f(x)가 O(g(x))라는 건 f(x)/g(x)가 어떤 상수 C에 대해 “모든 x에 대해서 f(x)/g(x) < C”를 만족한다는 뜻임. 컴과에서는 f(x)가 특정 알고리즘의 연산 횟수와 같은 복잡성을 뜻하는 경우가 많음
- Big-O Notation 설계는 여러 해석이 가능함. 예를 들어 어떤 알고리즘을 Turing Machine의 동작 스텝수로 정의하면, log 시간 알고리즘이란 게 있을 수 없고 O(log n)는 O(1)로 취급됨
- 전산 1학년 필수 과목에서 배웠음. 별거 없고, 입력 데이터가 많아질 때 연산량이 어떻게 늘어나는가만 서술하는 개념임. 겉보기엔 어려운데 실제론 아주 간단하고 명쾌함
동적 시각화가 이해에 엄청난 도움이 되었음. 이처럼 더 많은 레슨/자료를 만들어주길 바람
- 그 반응이 참 고맙고 기쁨
Big-O Notation 관련 스레드가 올라올 때마다 혹시 누가 이 개념이 애니메이션 The Big O와 어떻게 연결되는지 설명해주길 기대하게 됨. 아직도 그 애니 내용이 뭔지 잘 모르겠음
- (맥주 4캔 벌컥벌컥)<p>좋아 들어봐. 그 애니는 Pacific Rim, Dark City, The Matrix 세 가지를 차례로 섞어놓은 것 같은 내용임
개인적으로 Big O Notation을 가장 효과적으로 이해하는 방법은 일상을 빗대어 연결해보는 것임
아름다운 자료라 생각함. 신호를 보내봤는데 잘 전달됐길 바라며, 괜히 도파민 한 스푼 얻은 느낌임
- 잘 도착했음. 고마움 <3

답변달기