자료구조, 알고리즘, 시간복잡도 간단정리

<자료구조, 알고리즘, 시간복잡도>

* 자료구조란?

자료구조란 데이터를 표현하거나 저장하는 방법이다. 

1. 단순구조
기본자료형 (2진수, 정수,실수, 문자, 문자열 )

2. 파일구조 
순차파일, 색인파일, 직접파일 

3. 선형구조 = 데이터간 관계가 1:! 
리스트, 연결리스트, 데크, 스택, 큐 

4. 비선형구조 = 데이터간 관계가 1:N / N:M
트리 - 일반트리, 이진트리 
그래프 - 방향그래프, 무방향 그래프 

* 알고리즘이란?

자료구조가 데이터를 표현하거나 저장하는 방법이라면 
알고리즘은 데이터를 이용하여 문제를 해결하기 위한 절차나 방법. 

* 좋은 알고리즘을 위한 5가지 조건 

1. 입력 - 0개이상의 입력 
2. 출력 - 1개 이상의 출력 
3. 명확성 - 각 명령어의 의미는 모호하지 않고 명확성
4. 유한성 - 한정된 수의 단계후에는 반드시 종료되어야 한다. 
5. 유효성 - 각 명령어들은 실행가능한 연산이어야 한다. 

* 알고리즘 표현방법 

1. 자연어
2. 순서도 
3. 의사코드
4. 프로그래밍 언어

* 시간복잡도 / 공간복잡도

효과적인 알고리즘을 얻기위해 알고리즘의 성능을 분석하고 평가할수 있어야한다. 
컴퓨터에서는 시간과 메모리 두 자원이 알고리즘의 효율성을 측정하는 척도가 된다. 

알고리즘의 수행시간을 분석한 결과를 "시간 복잡도" 라고 하며,  => 명령어의 실행횟수 
메모리 사용량을 분석한 결과를 "공간 복잡도" 라고 한다. => 메모리 사용량 

효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성

void f(int n){
     int cnt = 0;      //1
     int sum = 0;      //1
     for(int i=0; i<n l i++){
         cnt++;      //n
         sum += i;      //n
     }
}

위 알고리즘의 시간복잡도함수는 f(n) = 2n + 2 이다. 

n은 입력개수를 뜻하며, n이 증가하면 그에 비례하여 시간도 증가한다. 

* big-o 표기법 

알고리즘의 시간복잡도와 공간복잡도를 표현하는 대표적인 방법에는 big-o 표기법이 있다. 
big-o 표기법은 알고리즘 실행에 있어 최악의 경우를 나타낸다. 
아무리 최악이라도 이정도의 성능은 보장! 이라는 뜻. 

오메가 표기법 -> 알고리즘 최상의 실행시간
세타표기법 -> 알고리즘 평균 실행시간

즉, 시간또는 공간의 상한선을 두는 것이다. 

* 효율적인 순서 

O(1)
     상수형 
     입력값이 아무리커도 실행시간 일정, 최고의 알고리즘 
O(log n)
     로그형
     실행시간은 입력값에 영향을 받지만 큰 n에 대해서도 매우빠르다. 이진검색 알고리즘의 수행시간
     업/다운 게임. bfs 알고리즘이 대표적
O(n)
     선형 
     입력값에 비례해서 수행시간이 증가한다. 
     range길이가 n개인 for문이 대표적
O(n*log n)
     선형로그형
     대부분의 효율좋은 정렬알고리즘의 수행시간.
     비교 기간 정렬알고리즘은 아무리 좋은 알고리즘도 O(n*log n) 보다 빠를 수 없다. 
O(n^2)
     제곱시간(2차형)
     버블정렬같은 비효율적인 알고리즘의 수행시간
     이중for문
O(2^n)
     지수형 
     재귀로 구현하는 피보나치 수열은 O(2^n) 의 대표적인 알고리즘이다. 시간이 기하급수적으로 늘어난다. 
O(n!)
     팩토리얼형


* 최선, 평균, 최악의 경우 
일반적으로 알고리즘을 평가할때 최선의 경우와 최악의 경우를따진다. 
배열내의 어떠한 x 값을 찾을때 첫번째 index부터 순차적으로 찾는 알고리즘이 있다. 

최선의 경우 첫번째 index에 x값이 위치하여 한번에 찾을 수 있거나 
최악의 경우 index 마지막에 x값이 위치하여 배열의크기 (n) 만큼 전부 찾아야 할것이다. 

해당 알고리즘의 최선의 경우에는 O(1), 최악의 경우에는 O(n) 이라고 말할수 있을 것이다. 


* 자바 컬렉션 자료구조별 시간 복잡도

	add()	remove()	get()	contains()
ArrayList	O(1)	O(n)	O(1)	O(n)
LinkedList	O(1)	O(1)	O(n)	O(n)

*리스트는 remove와 get에서 어레이리스트와 연결리스트간에 차이가 있으며
contains는 모두 O(n)이다. 

 

	push()	pop()	peek()	search()
Stack	O(1)	O(1)	O(1)	O(n)

*스택은 검색만 o(n), pop,peak는 o(1) 이다.

	add()	contains()	next()
HashSet	O(1)	O(1)	O(h/n)
LinkedHashSet	O(1)	O(1)	O(1)
TreeSet	O(logn)	O(logn)	O(logn)

HashSet은 contains() 시간복잡도가 O(1)로서 List 보다 검색이 더 효율적이다. 
TreeSet(이진트리)는 예외로 모두 O(logn)이다. 

	offer()	peak()	poll()	size()
PriorityQueue	O(logn)	O(1)	O(logn)	O(1)

 

	get()	contains()
HashMap	O(1)	O(1)
LinkedHashMap	O(1)	O(1)
TreeMap	O(logn)	O(logn)

*Map도 contains() 검색효율이좋다. 
treemap은 O(logn) 이다.


<java 컬렉션 프레임워크> 

list - 순서가 있는 데이터의 집합. 중복허용. 리스트, 스택, 큐 
set - 순서가 없고 중복을 비허용
map - key, value 쌍. 순서없음. 키는 중복비허용, 밸류는 중복 허용

링크드 리스트는 자신과 연결된 다음요소의 주소값으로 구성되어 있음. 
이중연결리스트 - 이전요소에 대한 참조된 추가버전 (링크드 리스트 단점보완)
별도의 저장공간이 더 필요하다. 

어레이리스트 - 검색빠름, 추가삭제(느림) - 순차적인 추가삭제는 더 빠름. 
링크드리스트 - 검색느림, 추가삭제(빠름)

스택
lifo 방식

큐
fifo 방식

tree셋은 이진검색트리라는 자료구조를 가진 컬렉션
이진검색트리는 정렬, 검색, 법위검색에 높은성능을 보이는 자료구조. 
각 노드에 최대 2개의 노드를 연결할 수 있으며, 
루트라고 불리는 하나의 노드에서 시작하여 확장가능.
부모노드의 왼쪽에는 부모노드보다 작은값, 오른쪽에는 큰값 저장. 


해시맵과 해시테이블. 
key/value


1. 검색하고자 하는 키로 해시함수를 호출한다.
2. 해시함수의 계산결과인 해시코드를 이용해서 해당값의 위치 찾음.


1.14 컬렉션 클래스 정리&요약
ArrayList  - 배열기반, 데이터의 중간 추가와 삭제에 불리, 순차적인 추가/삭제는 가장 빠름. 
임의의 요소에 대한 접근성이 좋음 
LinkedList  - 연결기반, 데이터의 중간 추가와 삭제에 유리, 임의의 요소에 대한 접근성이 나쁨. 
Stack  - LIFO 형식의 컬렉션클래스
Queue  - FIFO 형식의 컬렉션 클래스

HashSet  - 대표적인 set 컬렉션클래스 
TreeSet  - 이진검색트리형태의 set, 정렬,검색, 범위검색에 좋음
LinkedHashSet  - HashSet에 저장순서유지기능을 추가 

HashMap  - 배열과 연결이 결합된 형태, 추가,삭제,검색,접근성 모두 뛰어남. 검색에는 최고성능
TreeMap - 연결기반, 정렬과 검색(특히 범위검색)에 적합. 검색성능은 HashMap 보다 떨어짐. 
LinkedHashMap - HashMap 에 저장순서유지기능을 추가 



<정렬 알고리즘>
기본 정렬 알고리즘 요약정리 (선택, 삽입, 버블, 합병, 퀵)

1. 선택정렬 
선택정렬은 현재위치에 들어갈 값을 찾아 정렬하는 방식. 

최소선택정렬 = 오름차순 
최대선택정렬 = 내림차순 

1-맨앞 인덱스에서부터 이를 포함한 이후의 배열값중 가장 작은값찾음. > 작은값을 현재 인덱스로 옮김. 
2-다음 인덱스부터 위의 과정 반복.

이알고리즘을 n-1개, n-2개....1개 씩 비교를 반복한다. 
배열이 어떻게 되어있던 전체 비교를 진행하므로 시간복잡도는 O(n^2) 이다. 

시간복잡도는 O(n^2) / 공간복잡도는 하나의배열에서만 하므로 O(n)
 

2. 삽입정렬
삽입정렬은 현재위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아 
그 위치에 삽입하는 방식이다. 

1-삽입정렬은 두번째 인덱스부터 시작한다. 
현재 인덱스값은 별도의 삽입변수에 저장해주고  비교인덱스를 현재인덱스-1로 잡는다. 

2-삽입변수와 비교인덱스값을 비교한다. 

3-삽입변수의 값이 더 작으면 비교인덱스위치를 -1을 하여 비교를 반복한다. 

4-삽입변수가 더 크면 비교인덱스 + 1에 삽입변수를 저장한다. 

이 정렬알고리즘의 경우 최악의 경우(역으로 정렬되어 있을때) 선택정렬과 마찬가지로 O(n^2) 이지만
이미 정렬되어 있는 경우는 한번밖에 비교를 하지않아 O(n) 이다. 

하지만 빅오 표기법에서는 최악을 기준으로 평가하므로 삽입정렬의 시간복잡도는 O(n^2) 이다. 


3. 버블정렬

버블정렬을 매번 연속된 두개 인덱스를 비교하여 정렬 하는 방식이다. 

1- 두번째 인덱스부터 시작한다. 현재인덱스값과 바로 이전의 인덱스값을 비교한다. 
2- 이전 인덱스값이 더 크면 현재 인덱스값과 바꿔준다. 
3- 현재 인덱스값이 더 크면 교환하지 않고 다음 두 연속된 배열값을 비교한다. 

이 알고리즘은 1부터 비교를 시작하여 n-1개, n-2개... 1개씩 비교를 반복
선택정렬과 마찬가지로 시간복잡도는 O(n^2) 이다. 



4. 합병정렬
합병정렬은 분할정복 방식으로 설계된 알고리즘이다. 
분할정복은 큰 문제를 반으로 쪼개 문제를 해결하는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을때 까지
반복한다.

입력으로 하나의 배열을 받고, 연산중에 두개의 배열로 계속 쪼개나간뒤, 합치면서 정렬해 
최후에는 하나의 정렬을 출력한다. 

1-현재배열을 반으로 쪼갠다. 
2-배열의 시작위치 + 종료위치 / 2 하여 그위치를 기준으로 다시 나눈다.
3-이를 쪼갠 배열의 크기가 0이거나 1일때까지 반복한다. 
4-쪼객 다음 다시 합치기 시작 이때 두 배열의 값을 비교하여 작은값을 앞에, 큰값을 뒤에놓고 붙인다.
5.다시 붙이기시작. 두배열의 앞부분부터 비교하여 작은값을 앞에다 붙이는방식으로 두배열 함칩.
6. 최종적으로 하나의 배열이 될때까지 이 방식으로 합칩. 

합병정렬의 시간복잡도는 O(n log n) 이다.


5.퀵 정렬
퀼 정렬또한 분할정복을 이용하여 정렬을 수행하는 알고리즘 이다. 
피봇포인트라고하는 기준이 되는 값을 하나 설정하는데  이 값을 기준으로 작은값은 왼쪽. 큰값을 오른쪽으로 
옮기는 방식으로 정렬을 진행한다. 이를 반복하여 분햘된 배열의 크기가 1이 되면 배열이 모두 정렬된 것이다. 

1-피봇포인트로 잡을 배열의 값을 하나 정한다. 
2-비교를 진행하기위한 가장 왼쪽배열의 인덱스를 저장,  가장 오른쪽 배열의 인덱스를 저장. 
.... 잘이해가 안됨.

퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘이다. 
각 정렬은 배열의 크기 n 만큼 비교하며, 이를 총분할깊이인 log n만큼 진행하므로 
시간복잡도는 O(n log n) 이다. 

다만 퀵정렬에는 최악의 경우가 존재하는데 배열이 이미 정렬되어 있는경우이다. 
이 경우 분할이 n 만큼 일어나므로 시간복잡도는 O(n^2) 이다. 

이를 방지하기위해 앞서 중간값이나 랜덤값으로 피봇포인트를 정하기도 한다. 

최악의 경우 합병정렬보다 느린 알고리즘이지만, 발생하기 쉽지 않은 경우이고,
일반적으로 퀵 정렬이 합병정렬보다 20%이상 빠르다고 한다. 

<정리>

정렬	최상	평균	최악	최악의 공간복잡도
퀵 정렬	O(nlogn)	O(nlogn)	O(n^2)	O(nlogn)
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)	O(n)
힙 정렬	O(n)	O(nlogn)	O(nlogn)	O(n)
버블 정렬	O(n)	O(n^2)	O(n^2)	O(1)
삽입 정렬	O(n)	O(n^2)	O(n^2)	O(1)
선택 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)

-----------------------------------------------

[Java] Arrays.sort()와 Collections.sort()의 시간복잡도 비교

정렬 방식 시간 복잡도
Arrays.sort()
DualPivotQuicksort(듀얼 피봇 퀵 정렬)
평균 : O(nlog(n)) / 최악 : O(n^2)

Collections.sort()
TimeSort (삽입정렬과 합병정렬을 결합한 정렬)
평균, 최악 : O(nlog(n))