정렬 알고리즘과 검색 알고리즘 조합 빅오(Big O) 분석 (2)

정렬 알고리즘과 검색 알고리즘 조합 빅오(Big O) 분석 (2)

---

정렬 알고리즘 (Sorting Algorithms)

• Bubble Sort (버블 정렬)
  • 인접한 두 원소를 비교하며 정렬하는 방식으로, 시간복잡도가 O(n²)으로 비효율적입니다.
• Selection Sort (선택 정렬)
  • 가장 작은 원소를 찾아 앞쪽으로 이동시키는 방식으로, O(n²)의 시간복잡도를 가집니다.
• Insertion Sort (삽입 정렬)
  • 새로운 원소를 적절한 위치에 삽입하는 방식으로, 최선의 경우 O(n)의 성능을 보입니다.
• Merge Sort (병합 정렬)
  • 분할 정복 방식으로 동작하며, 안정적인 O(n log n) 성능을 제공합니다.
• Quick Sort (퀵 정렬)
  • 피벗을 기준으로 분할하여 정렬하는 방식이며, 평균 O(n log n)의 성능을 보이지만 최악의 경우 O(n²)입니다.
• Heap Sort (힙 정렬)
  • 힙(Heap) 자료구조를 이용해 정렬하는 방식으로 O(n log n)의 성능을 가집니다.
• Counting Sort (계수 정렬)
  • 숫자의 개수를 세어 정렬하는 방식으로, 시간복잡도는 O(n + k)입니다.
• Radix Sort (기수 정렬)
  • 자릿수를 기준으로 정렬하는 방식으로, 시간복잡도는 O(nk)입니다.
• Bucket Sort (버킷 정렬)
  • 데이터를 여러 개의 버킷(bucket)으로 나누어 정렬하는 방식이며, 최선의 경우 O(n), 최악의 경우 O(n²)입니다.

---

검색 알고리즘 (Search Algorithms)

• Linear Search (선형 탐색)
  • 모든 원소를 하나씩 확인하는 방식으로, O(n)의 시간복잡도를 가집니다.
• Binary Search (이진 탐색)
  • 정렬된 배열에서 중앙값을 기준으로 탐색하는 방식이며, O(log n)의 성능을 가집니다.
• Jump Search (점프 탐색)
  • 특정 간격(√n)만큼 건너뛰며 탐색하는 방식으로, O(√n)의 성능을 가집니다.
• Interpolation Search (보간 탐색)
  • 값의 분포를 고려하여 탐색하는 방식으로, 평균적으로 O(log log n)의 성능을 보입니다.
• Exponential Search (지수 탐색)
  • 지수적으로 증가하는 간격으로 탐색한 후, 이진 탐색을 수행하는 방식으로 O(log n)의 성능을 가집니다.

---

정렬 알고리즘과 검색 알고리즘을 조합한 빅오(Big O)

• 정렬 알고리즘	최악 시간복잡도	평균 시간복잡도	최선 시간복잡도	검색 알고리즘	검색 시간복잡도
  Bubble Sort	O(n^2)	O(n^2)	O(n)	Linear Search	O(n)
  Bubble Sort	O(n^2)	O(n^2)	O(n)	Binary Search	O(log n)
  Bubble Sort	O(n^2)	O(n^2)	O(n)	Jump Search	O(√n)
  Bubble Sort	O(n^2)	O(n^2)	O(n)	Interpolation Search	O(log log n)
  Bubble Sort	O(n^2)	O(n^2)	O(n)	Exponential Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Selection Sort	O(n^2)	O(n^2)	O(n^2)	Linear Search	O(n)
  Selection Sort	O(n^2)	O(n^2)	O(n^2)	Binary Search	O(log n)
  Selection Sort	O(n^2)	O(n^2)	O(n^2)	Jump Search	O(√n)
  Selection Sort	O(n^2)	O(n^2)	O(n^2)	Interpolation Search	O(log log n)
  Selection Sort	O(n^2)	O(n^2)	O(n^2)	Exponential Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Insertion Sort	O(n^2)	O(n^2)	O(n)	Linear Search	O(n)
  Insertion Sort	O(n^2)	O(n^2)	O(n)	Binary Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Merge Sort	O(n log n)	O(n log n)	O(n log n)	Linear Search	O(n)
  Merge Sort	O(n log n)	O(n log n)	O(n log n)	Binary Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Quick Sort	O(n^2)	O(n log n)	O(n log n)	Linear Search	O(n)
  Quick Sort	O(n^2)	O(n log n)	O(n log n)	Binary Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Heap Sort	O(n log n)	O(n log n)	O(n log n)	Linear Search	O(n)
  Heap Sort	O(n log n)	O(n log n)	O(n log n)	Binary Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Counting Sort	O(n + k)	O(n + k)	O(n + k)	Linear Search	O(n)
  Counting Sort	O(n + k)	O(n + k)	O(n + k)	Binary Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Radix Sort	O(nk)	O(nk)	O(nk)	Linear Search	O(n)
  Radix Sort	O(nk)	O(nk)	O(nk)	Binary Search	O(log n)
  ------------------	--------------	--------------	--------------	------------------	--------------
  Bucket Sort	O(n^2)	O(n)	O(n)	Linear Search	O(n)
  Bucket Sort	O(n^2)	O(n)	O(n)	Binary Search	O(log n)

view raw more.sort.search.algorithm.ko.md hosted with ❤ by GitHub

---

• 도움이 되셨으면 하단의 ❤️ 공감 버튼 부탁 드립니다. 감사합니다! 😄

view raw i.like.it.ko.md hosted with ❤ by GitHub