노트정리/자료구조
계산 복잡도 - 빅오 표기법(big O)
직접 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법으로 알고리즘의 복잡도 분석이 있다.이 방법에는 2가지 방법이 있는데 알고리즘의 수행시간을 분석하는 시간 복잡도 , 알고리즘이 사용하는 기억공간을 분석 하는공간 복잡도가 있다. 알고리즘 복잡도를 이야기할 떄는 대게 시간 복잡도를 뜻하며 시간 복잡도의 표시는 빅오 표기법(big-oh notation)으로 한다. 빅오 표기법(Big-Oh Notation) 1. 시간 복잡도 표기법시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시함.O(3n+2) = O(3n) = O(n)이 된다.2. 수학적 정의모든 N >= N0 에 대해서 f(N) n0인 모든 n에 대해 f(n) < c g (n)을 만족하는 2개의 양의 상수 c, n0 이 존재하면 ..
노트정리/알고리즘
병렬 알고리즘 - 병렬 컴퓨터
병렬 알고리즘- 여러 대의 컴퓨터를 사용하여 빠르게 처리하기 하기 위한걸 병렬 처리라고함. 병렬 컴퓨터에서 실행하도록 고안됨.병렬 컴퓨터병렬 컴퓨터는 CPU와 메모리 ,입출력 장치 등을 포함한 여러 개의 시스템들을 하나로 묶어서 구성하여 마치 하나처럼사용할 수 있는 컴퓨터를 말한다. 이러한 병렬 처리 구현을 위해 파이프라인 방식, 배열 프로세서, 다중 연산 기법 등을 사용한다. 구분 내용 SISD 일반적인 컴퓨터 구조( 폰 노이만 방식)단일 명령어 흐름에 따른 단일 데이터 흐름 컴퓨터하나의 명령에 따른 하나의 자료를 처리하는 구조병렬 처리는 파이프라인 구조로 구현 SIMD 단일 명령어 흐름에 따른 다중 데이터 흐름 컴퓨터하나의 명령에 따른 여러 자료를 동시에 처리하는 구조병렬 처리는 배열 처리와 벡터 처..
노트정리/알고리즘
확률적 알고리즘 과 유전 알고리즘
확률적 알고리즘알고리즘의 근본적인 부분에서 확률이 관계하고 있는 것을 확률적 알고리즘이라 함. 하지만 주어진 문제를 해결하는 알고리즘은결정론적 알고리즘으로 기술. 이는 항상 같은 결과를 출력하고 처리하기 때문이다. - 확률적 알고리즘은 항상 같은 결과를 출력하지 않음. 경우에 따라서 틀린 결과를 출력하거나 최적해가 아닌 근사해를 출력함.- 원하는 결과를 얻지 못할 확률이 매우 낮다는 조건하에서 주어진 문제를 해결하는데 활용함.- 난수를 필요로 함. 암호학 분야에서 매우 중요. 몬테카를로 , 라스베이거스 알고리즘이 있음. 몬테카를로 알고리즘 - 물리적, 수학적 시스템의 행동을 시뮬레이션하기 위한 계산 알고리즘이다.- 통계학적이며 일반적으로 무작위의 숫자를 사용한 비결정적인 방법. - 스타니스와프 울람이 모..
노트정리/알고리즘
NP - 완전 문제 근사 알고리즘
NP-완전 - NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합 , 모든 NP 문제를 다항시간 내에 NP-완전 문제로 환산 가능.- NP-완전 문제 중 하나라도 P에 속한다는 것을 증명하면 모든 NP 문제가 P에 속하기 때문에 P-NP 문제가 P=NP의 형태로 풀림.- 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어서 P-NP 문제는 P#NP 가됨. 쉬운 문제와 어려운 문제 판정 문제와 최적화 문제 가 있다.쉬운 문제 다항식 시간 알고리즘이 존재하는 문제 어려운 문제 다항식 시간을 초과하는 문제 판정 문제 문제의 해가 '예/아니오'로 나오는 문제 최적화 문제 최소치나 최대치를 구하는 형태의 문제 NP-완전성과 변환성 결정론적 알고리즘모..
오늘도 삽질
