아무거나

Selection Sort [선택정렬] Worst case performance : O(n^2) Best case performance : O(n^2) Average case performance : O(n^2) Worst case space complexity : O(n) total, O(1) auxiliary 선택정렬은 퍼포먼스가 n squared 로 좋지 않다. 하지만 구현이 쉬워서 많은 사람들이 사용하고 있다. [ 예제 ] 아래 그림의 4 6 1 3 5 2 리스트를 1 2 3 4 5 6 으로 차례가 맞게 정렬하자. 선택정렬의 예시를 알아보자. 선택정렬은 하나의 공간이 필요하다 그것을 Minimum value라는 공간이라고 한다. 그러면 처음 아이템부터 끝까지 비교하면서 해당 리스트를 정렬해보자. ..

Bubble Sort [거품정렬] performance : O(n^2) space complexity : O(1) * 시간복잡도가 O(n^2) 이므로 느리지만 코드가 단순하기 때문에 자주 사용된다고 한다. 거품정렬은 원소의 이동하는 모습이 거품이 수명으로 올라오는듯한 모습과 비슷하므로 지어진 이름이다. 해당 정렬의 목표는 인접한 두개의 자료를 비교해서 차순에 맞게 교환하는 작업을 정렬이 완료 될 때까지 해준다. 자료수에 한 개를 뺄 만큼 Looping을 하면서 서로 인접한 아이템을 swapping해주는 방법으로 해당 리스트를 정렬할 것이다. 즉, 아래와 같이총 4개의 아이템이 있으므로 우리는 총 3번(=n-1) Looping을 할 것이다. ( 예제 리스트: 6 5 3 1 ) [Loop Count : 1,..

Big-O Notation(빅오표기법) 알고리즘의 성능을 수학적으로 표현해주는 표기법, 이걸로 알고리즘은 시간과 공간복잡도를 표현할 수 있다. 그리고 알고리즘의 실제 러닝타임을 표시하는것이아니라 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는것이 목표이기때문에 상수와 같은 숫자들은 모두 1이 된다. * 성능 순서(오른쪽으로 갈수록 성능이 안좋음) - O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) 1. O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다. (Constant Time) [중요] - 입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다. - 알고리즘이 문제를 해결하는데 오직 한 단..