[Algorithm]

시간 복잡도

• 시간 복잡도는 알고리즘의 성능을 나타내는 척도
• 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행시간 분석
• 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 우수하다.

빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
• 함수의 상한을 나타냄
• 예를 들어 연산 횟수가 3𝑁^3 + 5𝑁^2 + 1,000,000
• 𝑁이 증가함에 따라서, 3𝑁^3을 제외한 다른 항의 영향력은 작아진다.
• Big-O 표기법에서는 차수가 가장 큰 항에서 계수를 제외하여 𝑂 𝑁^3 으로 표현된다.

버블 정렬(Bubble Sort)

• 단순히인접한두원소를확인하여,정렬이안되어있다면위치를서로변경한다.
• 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름이다.
• 시간복잡도𝑂 𝑁2 로비효율적인정렬알고리즘중하나다.

버블 정렬(Bubble Sort) 동작 방식

• 각 단계에서는 인접한 두 개의 원소를 비교하여, 필요시 위치를 변경한다.
  • 첫째와 둘째를 비교, 둘째와 셋째를 비교, 셋째와 넷째를 비교하는 방식이다.
  • 한번의단계가수행되면,가장큰원소가맨뒤로이동한다.
  • 따라서, 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외한다.

버블 정렬(Bubble Sort)의 시간 복잡도

• 최악의경우시간복잡도𝑂 𝑁2 을보장한다.
• 이미 정렬된 배열에 대해서 모든 비교가 필요하므로, 굉장히 비효율적인 정렬 알고리즘 중
  하나에 속한다.

// 버블 정렬 함수
function bubbleSort(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] < arr[j + 1]) { // 내림차순 예시
let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
} }
} }