- 게시됨
자바스크립트에서의 빅 오 표기법
- 작성자
- 이름
- Imamuzzaki Abu Salam
- https://x.com/ImBIOS_Dev
빅 O 표기법
빅 O 표기법은, 통칭 바흐만-란다우 표기법 또는 점근 표기법이라고 불리며, 알고리즘의 성능을 나타내는 방법입니다. 이는 알고리즘의 최악의 경우 시나리오를 설명하는 데 사용되며, 서로 다른 알고리즘의 성능을 비교하는 데 사용됩니다. 또한, 입력 크기에 따른 알고리즘 구현 방식을 설명합니다.
빅 O 표기법은 함수의 성장률에 따라 함수를 특징짓습니다. 동일한 성장률을 가진 작업은 동일한 순서로 간주됩니다. 특정 값이나 무한대로 인수가 향할 때 함수의 제한적인 동작을 설명하는 수학적 표기법입니다. 이는 입력 크기가 커짐에 따라 실행 시간 또는 공간 요구 사항이 어떻게 증가하는지에 따라 알고리즘을 분류하는 데 사용됩니다. O라는 문자는 함수의 성장률을 순서라고 부르기 때문에 사용됩니다.
반복
for 루프
for (let i = 0; i < n; i++) {
console.log(i)
}
위 코드는 n번 실행됩니다. 이 코드의 시간 복잡도는 O(n)입니다.
while 루프
let i = 0
while (i < n) {
console.log(i)
i++
}
위 코드는 n번 실행됩니다. 이 코드의 시간 복잡도는 O(n)입니다.
do while 루프
let i = 0
do {
console.log(i)
i++
} while (i < n)
위 코드는 n번 실행됩니다. 이 코드의 시간 복잡도는 O(n)입니다.
재귀
팩토리얼
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
위 코드는 n번 실행됩니다. 이 코드의 시간 복잡도는 O(n)입니다.
피보나치
function fibonacci(n) {
if (n <= 1) {
return n
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
위 코드는 n번 실행됩니다. 이 코드의 시간 복잡도는 O(n)입니다.
검색
선형 검색
function linearSearch(arr, value) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i
}
}
return -1
}
위 코드는 n번 실행됩니다. 이 코드의 시간 복잡도는 O(n)입니다.
이진 검색
function binarySearch(arr, value) {
let start = 0
let end = arr.length - 1
let middle = Math.floor((start + end) / 2)
while (arr[middle] !== value && start <= end) {
if (value < arr[middle]) {
end = middle - 1
} else {
start = middle + 1
}
middle = Math.floor((start + end) / 2)
}
if (arr[middle] === value) {
return middle
}
return -1
}
위 코드는 log(n)번 실행됩니다. 이 코드의 시간 복잡도는 O(log(n))입니다.
정렬
버블 정렬
function bubbleSort(arr) {
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
위 코드는 n^2번 실행됩니다. 이 코드의 시간 복잡도는 O(n^2)입니다.
선택 정렬
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let lowest = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j
}
}
if (i !== lowest) {
let temp = arr[i]
arr[i] = arr[lowest]
arr[lowest] = temp
}
}
return arr
}
위 코드는 n^2번 실행됩니다. 이 코드의 시간 복잡도는 O(n^2)입니다.
삽입 정렬
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i]
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j]
}
arr[j + 1] = currentVal
}
return arr
}
위 코드는 n^2번 실행됩니다. 이 코드의 시간 복잡도는 O(n^2)입니다.
병합 정렬
function mergeSort(arr) {
if (arr.length <= 1) return arr
let mid = Math.floor(arr.length / 2)
let left = mergeSort(arr.slice(0, mid))
let right = mergeSort(arr.slice(mid))
return merge(left, right)
}
function merge(left, right) {
let results = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
results.push(left[i])
i++
} else {
results.push(right[j])
j++
}
}
while (i < left.length) {
results.push(left[i])
i++
}
while (j < right.length) {
results.push(right[j])
j++
}
return results
}
위 코드는 n log(n)번 실행됩니다. 이 코드의 시간 복잡도는 O(n log(n))입니다.
퀵 정렬
function pivot(arr, start = 0, end = arr.length + 1) {
let pivot = arr[start]
let swapIdx = start
function swap(array, i, j) {
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
for (let i = start + 1; i < arr.length; i++) {
if (pivot > arr[i]) {
swapIdx++
swap(arr, swapIdx, i)
}
}
swap(arr, start, swapIdx)
return swapIdx
}
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
let pivotIndex = pivot(arr, left, right)
quickSort(arr, left, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, right)
}
return arr
}
위 코드는 n log(n)번 실행됩니다. 이 코드의 시간 복잡도는 O(n log(n))입니다.
빅 O 팁
- 산술 연산은 상수입니다.
- 변수 할당은 상수입니다.
- 배열(인덱스로) 또는 객체(키로)의 요소에 접근하는 것은 상수입니다.
- 루프에서 복잡도는 루프의 길이에 루프 내에서 발생하는 작업의 복잡도를 곱한 값입니다.