알고리즘 관련 개념

알고리즘이란 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현,

일련의 절차를 정형화시켜놓은 것.

 

순서도:

조건은 다이아몬드 모양의 기호사용. 분기를 의미.

조건 true/false에 따라 다르게 처리를 표현

처리결과를 출력하는 도형이 존재함

 

빅오:

빅오표기법은 최악의 상황일때를 고려

빅오표기법 중 가장 긴 실행시간 : O(N^2)

빅오표기법 중 가장 짧은 실행시간: O(logN)

 

검색알고리즘에 이진검색 특징:

전제조건은 데이터가 키값으로 이미 정렬되어 있어야 한다

a[pc] < key일때 검색 범위를 중앙 요소 a[pc+1]로 좁힌다

a[pc] > key일때 검색 범위를 중앙 요소 a[pc-1]로 좁힌다

시간의 복잡도: log2N

 

정렬 알고리즘:

핵심요소: 1.교환, 2.선택, 3.삽입

정렬은 키의 대소관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업

정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘을 내부정렬

정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘을 외부정렬

 

알고리즘은 시간의 복잡도와 공간의 복잡도가 있으며,

시간복잡도는 cpu의 처리시간,

공간복잡도는 ram의의 사용량

 

 

 

버블정렬

버블정렬이 수행시간이 제일 짧다.

퀼 정렬이 버블정렬보다 수행시간 빠름

정렬을 하는 방법은 선택, 버블, 퀵 등의 방법이 있음

 선택 정렬의 수행시간이 버블 정렬보다 느림