Hyun's Wonderwall

Asymptotic Analysis 점근적 분석- Order of growth가 관심사.- 이론적으로 수행 시간을 분석: n에 대한 함수로 알아낸다. 최고차항이 결정.- 시간복잡도 비교: 1  Asymptotic Notations 점근적 표기- Big-Oh, Big-Omega, Theta, small-oh, small-omega Big O: f(n) = O(g(n))이면 g(n)은 f(n)의 상한. upper bound.small o: f(n) = o(g(n))이면 f(n)은 g(n)보다 느리다Big Ω: f(n) = Ω(g(n))이면 g(n)은 f(n)의 하한. lower bound.small ω: f(n) = ω(g(n)) 이면 f(n)은 g(n)보다 빠르다.Theta Θ: f(..

재귀적 알고리즘분할 정복의 핵심 아이디어- 큰 문제를 작은 문제들로 분할한다. (상수 비율로) 상수나 변수로 - 각 작은 문제들을 재귀적으로/명시적으로 푼다- 작은 문제들을 결합하여 처음 문제를 푼다. Merge Sort 합병정렬MERGE-SORT A[1..n]    1. If n=1, done    2 .Recursively sort A[1.. ⌈n/2⌉] and A[⌈n/2⌉+1..n]    3. Merge the 2 sorted listsKey Subroutine: MERGE (결합 단계) Merge 합병정렬 수도 코드MERGE(A,p,q,r) n1 = q - p + 1 # 왼쪽 부분리스트 원소의 개수 n2 = r - q # 오른쪽 부분리스트 원소의 개수 ..

1단원알고리즘 과목에서 공부할 내용- 알고리즘 표현: 문제를 정확하고 추상적으로 정의하는 것, 알고리즘을 수도코드로 나타내는 것- 알고리즘 유효성: 알고리즘이 옳다는 것을 증명- 알고리즘 분석: 시, 공간 복잡도.- 알고리즘 설계: 고전적인 알고리즘. 메타 알고리즘. 어떤 상황에 사용? 알고리즘이란?- 절차의 순서. 주어진 문제에 대해, 조건 만족 위해. 입력. 출력. 자료구조와 연관. 알고리즘 분석- 성능과 리소스 사용량 중요. 그외에 정확성. 간결성. 신뢰성 등.. 왜 알고리즘과 성능을 공부?- 확장성 이해 도와줌. 실행 가능/불가능 알수있. 성능이 가치판단의 기준이 됨. 등2단원Pseudocode: 알고리즘 표현을 위해 설계되었음. 컴파일되지는 않음. 삽입정렬 In..