160809(화) - 알고리즘 for Java

알고리즘 for Java

알고리즘에 대해서 학부생일 때 보다 아주 쬐끔이라도 더 깊게 공부해보기 위하여 정리한다.

이미 알고있는 개념들에 대해서는 스킵하고 모르는것 위주로 나열되어 있다.

추상 데이터형(ADT : Abstract Data Type)

원시 데이터 : 시스템이 기본연산(덧셈, 뺄셈 등) 지원

사용자 정의 데이터 : 우리가 연산을 정의해야 한다.

- 실제로 사용될 때 구현될 수 있다.

- 보통의 사용자 정의 데이터형은 연산과 함께 정의된다.

- 문제를 푸는 과정을 단순화 시키기 위하여 "데이터구조 + 연산" 인 것을 "추상 데이터형"이라고 한다.

구성

1. 데이터의 선언

2. 연산의 선언

ex) 연결리스트, 스택, 큐, 우선순위 큐, 이진트리, 딕셔너리, Union, Find, 해시 테이블, 그래프 등

알고리즘

알고리즘은 주어진 문제를 풀기 위한 단계별 지시사항들이다.

수행시간 분석

문제의 크기(input의 크기)가 증가함에 따라 처리 시간이 얼마나 증가하는지를 분석

이상적인 알고리즘간의 분석

실행시간 : 컴퓨터에 따라서 실행 시간이 달라짐

실행된 구문의 수 : 언어나 개발자 스타일에 따라서 달라짐

※ 주어진 알고리즘의 수행 시간을 입력크기 n에 따른 함수 f(n)으로 표현하고 수행시간에 따라서 이 함수들을 비교

증가율

입력하는 값에 따라 수행시간이 증가하는 비율

※ 차수가 낮은 항들은 무시하고 가장 큰 증가율을 갖는 항을 근사치로 잡는다.

빅-오 표기법

- tight한 상한

- f(n) = O(g(n)) : n의 값이 클 때, f(n)의 상한이 g(n)

    n의 값이 클 때, f(n)에서 최대의 증가율이 g(n)

※ 목표는 "f(n)과 크거나 같은 최소의 증가율 g(n)을 찾는 것" !!!