ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법

추상화(Abstraction) - 중요한 속성만 포함하는 개체.

• 즉 가장 중요한 것에 초점을 두고 그 이외의 부가적인 것은 무시함.

ADT - Abstract Data Type

한 개의 특별한 데이터 타입의 데이터 표현과 그 타입의 연산을 제공하는 부 프로그램만을 포함하는 클로저이다. 한마디로 사용자에게는 연산에 대한 형식과 제약조건만 알려주고 실제로 어떻게 처리되는지는 표현하지 않는 기능

• 타입 객체의 표현은 숨겨지고 타입의 정의에서 연산 제공
• 타입 선언과 연산들은 단일 구문 단위에 포함

자바의 클래스 타입이라 볼 수 있음 

ADT에서 중요한 것은 어떻게 구현되는지는 몰라도 무엇을 하는지 알면 사용자는 만들 수 있다는 점.

복잡도 (Complexity)

프로그램의 실행이 얼마나 오래 걸리는가 (= time complexity)

얼마나 많은 메모리를 사용하는가 (= space complexity)

왜 분석할까?

• 실제로 실행하기 전에 구현할 알고리즘을 결정
• 실제 실행시키지 않고  주어진 코드에서 병목현상을 찾을 수 있음

공간복잡도 (Space Complexity)

주어진 알고리즘을 실행시키기 위해 필요한 space는 다음과 같이 두 가지로 분류해 볼 수 있다.

1. 알고리즘과 무관한 부분: 알고리즘의 특성과는 무관한 부분으로 프로그램 코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로 하는 공간 등이 이에 포함된다.
2. 알고리즘과 밀접한 부분: 알고리즘의 특성과 밀접한 관계가 있는 부분으로서 문제를 해결하기 위해 필요로 하는 공간을 의미한다. 즉, 변수를 저장하기 위한 공간이나 순환 프로그램일 경우, recursion stack 등이 이에 포함된다.

일반적으로 알고리즘의 공간 복잡도를 분석할때는 위의 두가지중 두 번째의 것을 계산하게 된다. 즉, 알고리즘이 문제를 해결하기 위해서 반드시 필요한 부분만을 계산함으로써 주어진 알고리즘의 공간 복잡도를 계산한다.

시간복잡도 (Time Complexity)

시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는지를 센 결과(frequency count)에 각 명령어의 실행시간(execution time)을 곱한 합계를 의미한다. 그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다.

 이와 같이 알고리즘을 이루는 명령어들의 실행횟수를 계산하여 알고리즘의 시간

복잡도를 구하는 일을 알고리즘의 분석(analysis of algorithm)이라고 한다. 또한, 알고리즘의 분석은 일반적으로 공간 복잡도 보다는 시간 복잡도를 통해서 이루어진다.

 빅 오 분석법 (Big-O Analysis)

빅 오 분석법은 입력 값의 개수에 따라서 알고리즘의 성능을 분석하는 방법. 이 방법을 통해서 간단하게 알고리즘의 성능을 따져볼 수 있음.

Big-O 는 worst case를 기준으로 함. 계산할 때, 차수가 가장 높은 최고차항만 두고 나머지는 버림

O(1): constant O(n): linear O(nlogn): O(n^2): quadratic O(2^n): expoential