Computer Science/자료구조 (11) 썸네일형 리스트형 Algorithm Analysis 1. Algorithm Efficiency - A, B 두가지 알고리즘이 있을 때 알고리즘을 선택하는 기준은? 컴퓨터 프로그램 디자인의 목표 1) 알고리즘을 이해하기 쉽게, 코딩하기 쉽게, 디버그하기 쉽게 디자인하는 것 2) 컴퓨터의 resources를 효율적으로 활용할 수 있게 하는 것 2)이 자료구조와 알고리즘 분석의 주요 관심사! 알고리즘 cost를 어떻게 측정할 것인가? 2. Measure Efficiency 2-1. Measuring Efficiency의 정의 : running time depends on "size" of the input(n) : T(n) - we count the number of basic operations T(n) : n! > 2^n > 2n^2 > 5nlogn > 2.. Mathematical Preliminaries 1. Set Concepts and Notation set notation => 중학교 때 배운 것..아재요.. powerset => 한 집합의 가능한 모든 부분 집합(subset)들의 집합 multiset => set 내부의 복제품을 가진 것 (ex. {a, a, b}, {a, a, b, b, b}) 2. Relation 2-1. 정의 relation R over a set S는 S로부터 만들어진 R의 규칙으로 정렬된 pair들. $R \times R \subseteq$ relation R over a set S ex) S = {1, 2, 3} Data structure & Algorithm 1. Data Structure 1-1. Selecting a Data Structure Data structure를 고르는데 고려해야할 것 -> DS별로 프로그램의 수행 시간이 달라진다. -> memory space와 time의 제한 조건에 따라 골라야하는 DS가 달라진다. DS(Data Structure)를 고르는 방법 1. 꼭 수행되어야 할 기본 연산을 알기 위해서 문제를 분석해야한다. 2. 각 연산에 주어진 메모리와 시간의 제한을 수량화한다. 3. 이러한 조건에 딱 맞는 DS를 고른다. 1-2. Costs and Benefits DS는 장점과 단점(costs and benefits)을 동시에 지닌다. => 다른 DS에 비해 모든 부분에서 뛰어난 DS는 존재하지 않는다. 각 문제(problem)는 .. 이전 1 2 다음
