#complexity
노트 4개
Computer Science › OSSU
OSSU 핵심 알고리즘 이론정렬·그래프·탐욕·동적 계획법·복잡도·NP-완전성까지 알고리즘 설계를 학습한다.
Algorithm › Sorting
기본 정렬: 버블·선택·삽입·셸·계수·기수 정렬구현이 단순한 O(n²) 비교 정렬 세 가지와 입력 상태에 따른 실제 속도 비교, 간격을 줄여 가며 삽입 정렬하는 셸 정렬, 비교 없이 정렬하는 계수 정렬·기수 정렬(LSD·MSD).
Algorithm
빅오 표기법과 시간 복잡도입력 크기가 커질 때 알고리즘의 연산량이 어떻게 늘어나는지를 최고차항으로 표현하는 방법과, 상한(O)·하한(Ω)·딱 맞는 범위(Θ)의 차이.
Algorithm
P, NP, NP-완전과 근사 알고리즘다항 시간에 풀 수 있는 문제(P), 답을 다항 시간에 검증할 수 있는 문제(NP), 환원으로 정의하는 NP-난해·NP-완전의 관계, 배낭·외판원·SAT 같은 대표 NP-완전 문제와 면접에서 위장된 형태를 알아보는 법, 그리고 정확한 해를 포기하거나 입력을 제한하는 근사·고정 매개변수·의사 다항 시간 같은 대응법.