알고리즘 총 정리

5장 

동적 계획 알고리즘은 최적성의원칙,최적 부분 구조의 특성을 가지고 있다.

 

1. 모든 쌍 최단 경로 문제를위한 플로이드 -워셜 알고리즘 // (n세제곱)
2. 연속 행렬 곱셉 //(n세제곱)
3. 배낭 문제 // C는 배낭의 용량 (nC)
4. 동전 거스름돈 // (nk) n은 거스름돈 액수이고 ,k는 동전종류

 

 

6장

추가 자료

버블정렬 -  모두 n제곱 // 추가공간 o(?) // 안정성 o

선택정렬
특징 입력이 거의정렬되어있든지 역으로 되어 있든지, 랜덤하게 되어있든지 항상 일정란 시간복잡도
즉 입력세 민감하지 않은 알고리즘이다. 

삽입정렬 
특징 입력에 따라다름 
거의 정렬된 입력에 대해서 다른 알고리즘 보다 빠르다
역으로 정렬된 입력에 대해서는 n제곱  

랜덤한 입력에 대해 원소 교환 횟수 최소

숼정렬 
입력크기가 크지않은 정렬할때 좋은 성능보임 

힙정렬

 

기수정렬

선형 크기의 추가메모리 필요, 입력크기가 커지면 캐시메모리 비효율적 사용

MSD<LSD 가 더빠름 

7장

 

다항식 시간복잡도를 가진 알고리즘으로 해결되는 문제의 집합 P문제 집합이라고한다.

문제 A에 대해서 만일 모든 NP문제가 문제A로 다항식 시간에 변환이 가능하다면

문제A는 NP-하드 문제 이다.

---일단 생랼

 

8장