알고리즘의 시간·공간 복잡도 효율성

컴퓨터 과학의 핵심 개념

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

빅오 표기법 소개

입력이 커질 때 시간·공간 증가를 측정
예: $O(n)$, $O(n^2)$, $O(\log n)$
'O'는 성장의 '차수'를 의미, 예: O(n) = 선형

시간 복잡도 - 사무실 비유

여러 빅오 복잡도를 보여 주는 차트

$O(1)$ - 상수 시간 - "빨리 훑어보기" - "상수"
$O(\log n)$ - 느린 증가 - "반으로 나누기" - "로그"
$O(n)$ - 선형 증가 - "문서 읽기" - "선형"
$O(n\log n)$ - 더 빠른 증가 - "더미 정렬" - "선형로그"
$O(n^2)$ - 제곱 증가 - "문서 비교" - "제곱"

공간 복잡도 - 사무실 비유

여러 빅오 복잡도를 보여 주는 차트

$O(1)$ - 상수 공간 - "책상 공간" - "상수"
$O(\log n)$ - 느린 공간 증가 - "최소 메모" - "로그"
$O(n)$ - 선형 증가 - "포스트잇" - "선형"
$O(n\log n)$ - 더 빠른 공간 증가 - "임시 더미" - "선형로그"
$O(n^2)$ - 제곱 공간 증가 - "비교 격자" - "제곱"

실습해 봅시다!

컴퓨터 과학의 핵심 개념

Preparing Video For Download...