시간 복잡도 - 대표적인 빅오(Big-O) 표기법

알고리즘 문제를 풀다 보면 시간 복잡도, 공간 복잡도를 계산할 줄 알아야 어떤 알고리즘이 더 효율적인지 판단할 수 있다.

빅오 표기법은 알고리즘 실행시간이 최악일 때를 표기하는 방법으로, 신뢰성이 떨어지는 오메가 표기법(실행시간 평균일 때를 표기하는 방법), 평가하기 어려운 세타 표기법(실행시간이 최상일 때 표기하는 방법)에 비해 성능을 예측하기 용이하여 주로 사용된다.

 

✏️ 복잡도란 ?

시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타내는 말로, 시스템 또는 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지 또는 개발하는데 어느 정도의 자원이 소요되는지 예측하는 데 사용.

 

✏️ 시간 복잡도란?

알고리즘의 실행시간, 즉 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 것을 의미.

 

시간 복잡도는 알고리즘의 실행시간이 하드웨어적 성능이나 프로그래밍 언어의 종류에 따라 달라지기 때문에 시간이 아닌 명령어의 실행 횟수를 표기한다.(= 점근 표기법) 

 

✏️ 대표적인 알고리즘의 빅오 표기법

O(1)	입력값(n)에 관계 없이 일정하게 문제 해결에 하나의 단계만을 거침 e.g. 스택의 삽입(Push), 삭제(Pop)
O(log₂n)	문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소 e.g. 이진 트리(Binary Tree), 이진 검색(Binary Search)
O(n)	문제 해결에 필요한 단계가 입력값(n)과 1:1의 관계를 가짐 e.g. for문
O(nlog₂n)	문제 해결에 필요한 단계가 n(log₂n)번만큼 수행됨 e.g. 힙 정렬(Heap Sort), 2-Way 합병 정렬(Merge Sort)
O(n²)	문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행됨 e.g. 삽입 정렬(Insertion Sort), 쉘 정렬(Shell Sort), 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 퀵 정렬(Quick Sort)
O(2ⁿ)	문제 해결에 필요한 단계가 2의 입력값(n)의 제곱만큼 수행됨 e.g. 피보나치 수열(Fibonacci Sequence)

 

 

 

+) 프로그래밍을 배우다 보면 기초 지식이 중요함을 많이 느끼는데 처음에 아무것도 모르고 추천 강의를 들을 땐 몰랐지만 이후 근본 C언어, 포인터, 알고리즘 등의 개념을 이해하는데 이 강의가 도움이 많이 되었다. 입문하시는 분들에게 정말 추천하는 하버드 명강의 CS50!!

아래 글의 강의 링크가 있고, 부스트코스에서 들으면 편집되어 자막이 달려 편하게 볼 수 있고 유튜브 CS50에 들어가면 계속 새로운 CS50 강의가 나온 걸 볼 수 있다. 크게 변하지 않는 기초 지식이라 어떤 걸 들어도 상관없을 것 같다. 아래 강의 추천!

 

2022.10.02 - [개발 지식] - [cs50 모두를 위한 컴퓨터 과학] 자료구조(Data Structure)

[cs50 모두를 위한 컴퓨터 과학] 자료구조(Data Structure)

 

 

 

참고 자료

김정준, 강윤석, 김용갑, 김우경, 길벗알앤디, 「2023 시나공 정보처리기사 필기」, 길벗, p286~287

사진 출처: https://studiousguy.com/big-o-notation-definition-examples/