알고리즘 (3) 썸네일형 리스트형 3. 점근적 표기법 - Big-Ω(빅 오메가), Big-θ(빅 세타), Big-O(빅 오) 점근적 표기법 - 알고리즘의 성능은 입력의 크기가 충분히 클 때의 성능이 중요하다. 그래서 알고리즘의 수행 시간은 항상 입력의 크기가 충분히 클 때를 분석한다. 즉, 입력이 \(\infty\)일 때를 분석하기 위해 점근적 분석을 해야한다. - 점근적 분석을 위해서 사용되는 표기법이 점근적 표기법이다. 점근적 표기법의 종류에는 여러 가지가 있지만 그 중 알고리즘에서 쓰이는 예는 \(\lim_{x\rightarrow \infty}\)을 사용한 점근적 표기법이다. 점근적 표기법에서 헷갈리지 말아야 할 것 증가율이 더 빠르다 = 알고리즘이 더 느리게 수행된다. 증가율이 더 느리다 = 알고리즘이 더 빠르게 수행된다. 1) Big - Ω (빅 오메가) 표기법 Ω(g(n)) 는 g(n)이라는 함수보다 증가율이 같거나.. 2. 알고리즘을 위한 수학적 배경지식 1) 연속적인 정수들의 합 2) 제곱수들의 합 최고차항만 중요하므로 위와 같이 근사한다. 3) K 제곱수들의 합 k에 2를 넣으면 2) 제곱수들의 합 식이 된다. 4) 2의 i 제곱수들의 합 5) 1) x 4) 1. 컴퓨터 알고리즘이란? 컴퓨터 알고리즘( Computer Algorithm )이란? 컴퓨터를 사용하여 어떤 문제를 해결하기 위한 단계적 방법에 대해서 서술하는 것이다. 컴퓨터를 사용하여 문제를 해결하는 순서 1) 문제 정의( Problem ) 전체 문제에 대한 Input과 Output 등을 정의한다. Input과 Output 중에 하나만 달라도 다른 문제이다. 2) 전략 결정( Strategy ) 3) 알고리즘 서술( Algorithm ) 알고리즘에 대한 Input과 Output, 그리고 의사코드를 정의한다. 4) 분석( Analysis ) 정확성( Correctness ), 시간 & 공간 복잡도 ( Time & Sapce Complexity ), 최적성( Optimality ) 등을 분석한다. 5) 구현( Implementa.. 이전 1 다음
