[자료구조 알고리즘] 빅오(Big-O)표기법
⭐️빅오(Big-O)표기법⭐️
알고리즘의 성능을 수학적으로 표현해주는 표기법
알고리즘의 시간과 공간복잡도를 표현
실제 러닝타임을 표시하는것 보다
데이터나 사용자의 증가율에 따른 알고리즘 성능 예측‼️
상수와 같은 숫자는 모두 1
O(1)
Constant Time Complexity
데이터 타입의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 뜻해요
사실상 가장 효율적이라고 생각이 들어요
데이터 크기가 n개의 크기와 상관없이 동일한 단계만 필요한 경우에 알고리즘이 상수 시간으로 실행된다~라고 말을 해요
배열의 크기가 100개 10000개 오억개라도 한 단계만 거치면 결과값이 나오기에 시간 복잡도를 그래프로 나타내면 아래쪽처럼
평평한 형태가 나와요!
아무리 데이터 크기가 커지더라도 알고리즘의 실행 시간이 변하지 않으므로 가장 효율적인 알고리즘입니다~
O(n)
Linear Time Complexity
데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘을 뜻해요
선형 시간 복잡도는 데이터 크기가 커지는 만큼 비례해서 늘어나는 알고리즘이며
아래와 같이 그래프가 나타나게 됩니다
O(n²)
Quardratic Time Complexity
선형 로그 시간 복잡도 다음으로 효율적인 시간 복잡도
데이터가 커질수록 시간복잡도도 부담스럽기 시작됨
나중에 갈수록 수직상승하게 되는 특성을 볼 수 있음
why?..
0 -> 1 -> 4 -> 9 -> 16 -> 25 -> 36 ->....식으로 올라가기 때문이다
O(nm)
위와 동일한 결과를 볼 수 있다
O(n³)
Polynomial / Cubic Time
O(2ⁿ)
Exponential Time
Ex) Fibonacci
이렇게 붙이면 피보나치 나선형이 만들어진다
0 -> 1 → 0 + 1 -> 1 + 1 → 2 + 1 -> 3 + 2 -> 5 + 3
데이터 증가량에따라 더 증가하는걸 알 수 있다
O(log n)
대표적인 예 - 이진검색
binary search
배열 반을 계속 나눠서 찾는 형식
값이 6이므로 5보다 작은 인덱스는 무시한체 5-9사이를 탐색한다
5-9사이의 인덱스는 7이므로 7보다 큰 인덱스는 무시하고 탐색한다
mid 값이 key값과 같다면 바로 return을하고
본 인덱스에서 인덱스에서 조건에 맞게끔 좌우 인덱스를 확인한다
Square root
⭐️참조 사이트 목록
⭐️영상 한 번 보세요 정말 강추 입니다⭐️
-한빛출판네트워크
[알고리즘] 시간 복잡도와 Big O 표기법
✅ Big O 표기법 알고리즘의 효율에서 가장 중요한 부분은 ‘n이 커질 때 알고리즘의 단계가 얼마만큼 증가하는가’이고, 이것을 잘 나타내는 빅 O 표기법을 사용합니다. ►[알고리즘 + 자료구조 =
m.hanbit.co.kr
https://github.com/kodecocodes/swift-algorithm-club/blob/master/Binary%20Search/BinarySearch.swift