본문 바로가기

algorithm10

알고리즘의 복잡도 입력 n에 대한 알고리즘의 성능을 평가하는 지표로써 시간복잡도와 공간 복잡도를 사용 시간복잡도 : 알고리즘의 수행시간을 평가 공간복잡도 : 알고리즘에 사용되는 메모리용량에 따라 평가 대표적인 복잡도 카테고리 O(log N) O(N) : 1차(linear) O(n log n) O(n^2) : 2차(quadratic) O(n^3) : 3차(cubic) O(2^n) : 지수(exponential) O(n!) 함수가 다항식일 때 최고차항만을 계산하여 표기함 시간복잡도 함수 증가율 * bigO 표기법 정의 : 주어진 복잡도함수 f(n)에 대해서 g(n) = O(f(n))을 만족한다(= g(n)의 증가율, 기울기가 낮다라고 말할 수 있다.) 정리하자면 시간복잡도에 대한 표기를 bigO 표기법으로 하며, bigO표기.. 2021. 9. 15.
선택 정렬(Selection Sort) 개인적으로 가장 직관적이고 구현하기 쉬운방법 인것같다 반복문이 돌때마다 최솟값을 찾아서 해당 index에 배치하면 된다 버블 정렬과 비슷하지만 교환이 일어나는 횟수는 버블정렬에 비해 적다 시간복잡도는 O(N^2)으로 10개의 배열의 경우 첫번째 배열에서 9개의 원소를 탐색 그다음은 8개 .. 7개.. 이런식으로 최악의 경우와 최선의 경우 상관없이 n-1 + n-2 + ... + 1 이런식이며 n(n-1)/2으로 시간복잡도는 O(N^2)이다. #include using namespace std; int main() { int arr[] = { 6,9,8,1,3,4,2,5,7 }; int arrSize = sizeof(arr) / sizeof(int); int tmp; for (int i = 0; i < a.. 2021. 9. 7.
삽입 정렬(Insertion Sort) 위 그림처럼 하나 key값이 파고들면서 제위치를 찾아간다고 생각하면 이해하기 쉽다 맨 첫번째 원소는 정렬 되어 있다고 가정한 후 두번째 원소부터 비교를 시작하는데 인덱스를 줄여나가면서 앞 원소가 더 큰값이라면 위치를 바꾸는 것을 반복 한 사이클이 돌 때마다 위 그림상 노란색으로 표시 되는 부분이 정렬 순서거 확정된다. 최악의 경우 시간복잡도는 O(N^2)이다. ex) 4 3 2 1을 삽입정렬한다고 가정하면 두번째 원소부터 4와 비교 -> 1번 연산 3,4, 비교 -> 2번연산 2,3,4,비교 -> 3번연산 즉, n(n-1)/2 와 같다. #include using namespace std; int main() { int arr[] = { 6,9,8,1,3,4,2,5,7 }; int arrSize = si.. 2021. 9. 7.
버블정렬(Bubble Sort) 정렬알고리즘을 이해하는 가장 쉬운 방법은 시각적으로 보는 것이라 생각한다. 인접한 요소끼리 대소를 비교해서 큰값을 뒤로 작은값을 앞으로 보낸다고 생각하면 쉽다 위 그림처럼 인접한 요소를 비교해 큰값을 뒤로 보내다 보면 1회차 반복이 끝났을 때 최댓값이 가장 마지막 자리로 가게된다 시간 복잡도는 O(N^2) #include using namespace std; int main() { int arr[] = { 6,9,8,1,3,4,2,5,7}; int arrSize = sizeof(arr) / sizeof(int); int tmp; for (int i = 0; i arr[j]) .. 2021. 9. 7.

티스토리툴바