시간 복잡도
-
[ 복잡도 ] 정렬 알고리즘의 복잡도Computer Science/자료 구조 2022. 12. 26. 21:43
정렬 알고리즘에 따른 복잡도 Algorithms space complexity time complexity 최악 최선 평균 최악 bubble O(1) O(n) O(n^2) O(n^2) heap O(1) O(n log n) O(n log n) O(log n) insertion O(1) O(n n) O(n^2) O(n^2) merge O(n) O(n log n) O(n log n) O(log n) quick O(log n) O(n log n) O(n log n) O(n^2) selection O(1) O(n^2) O(n^2) O(n^2) shell O(1) O(n) O(n^1.25) O(n^1.25) smooth O(1) O(n) O(n log n) O(n log n) 자료 구조 별 시간 복잡도 Big-O ..
-
[ 복잡도 ] 시간 복잡도와 공간 복잡도Computer Science/자료 구조 2022. 12. 26. 19:36
컴퓨터 과학에서 "복잡도"란, 문제를 풀거나 알고리즘을 푸는데 필요한 리소스를 나타낸다. 이러한 복잡도는 문제를 푸는데 걸리는 시간을 나타내는 "시간 복잡도"와 문제를 해결하는데 필요한 메모리/스토리지 양을 나타내는 "공간 복잡도" 이 두가지를 포함하여 다양한 측면에서 평가될 수 있다. 1. 시간 복잡도 시간 복잡도는 문제를 풀거나 알고리즘을 실행할 때 필요한 시간의 양을 나타내며, 일반적으로 입력 크기에 따라 측정된다. 이러한 시간 복잡도를 표기하기 위해 Big-O(상한 점근), Big-Ω(하한 점근), Big-θ(평균) 등의 표기법이 있는데, 주로 사용되는 것은 최악의 경우까지 고려할 수 있는 Big-O 표기법이다. big O notation : 빅-오 표기법에서는 복잡도는 입력 (n)에 따라 평가되..