자료구조 복습을 하면서 쓰는 글입니다.
먼저 첫번째로 공부할것은 알고리즘 분석에 대한 것입니다.
알고리즘 분석에 있어서 우선 우리는 좋은 알고리즘과 데이터구조를 설계해야만 합니다. 그러므로 알고리즘을 만든다면 실행시간과 기억장소 사용량을 최적화 할 수 있어야합니다.
그리고 실행시간을 따진다면 우리는 최악의 실행시간에 집중해야합니다. 평균실행시간도 있지만 구하기가 어렵고 보통은 최악실행시간이 용이하게 쓰입니다.
이러한 실행시간을 구할때 실험적 방법과 이론적 방법으로 2가지로 나뉘게 됩니다.
먼저 실험적 방법으로 실행시간을 구하는 것입니다.
- 프로그램 작성
- 다양한 크기의 입력으로 실행
- 실행시간 측정
- 도표로 작성
하지만 실험적 방법에는 여러가지 한계가 있습니다.
- 모든 입력을 다 고려하는 것이 아니기 때문에 특정한 입력에 대해서는 실행시간을 제대로 반영할 수 없습니다.
- 두 개의 알고리즘을 비교할 때, 동일한 하드웨어와 소프트웨어 환경이 필요합니다.
- 알고리즘을 완전한 프로그램으로 구현해야하는데 매우 어려울 가능성도 있습니다.
따라서 이론적 방법으로 실행시간 구하는 방법도 있습니다.
- 이러한 이론적 방법에서는 모든 입력 가능성을 고려합니다.
- 하드웨어, 소프트웨어에 무관하게 알고리즘의 속도를 평가합니다.
- 의사코드를 사용합니다.
여기서 의사코드가 나왔는데 그냥 알고리즘을 설명하기 위한 또 다른 고급언어라고 생각하시면 됩니다.
즉, 프로그래밍 언어 < 의사코드 < 자연어 이런 구조라고 생각하시면 됩니다.
여러가지 문법이 있지만 c언어나 python을 배우셨다면 의사코드를 따로 공부하지 않고도 충분히 이해할 수 있습니다.
다음은 원시작업입니다.
알고리즘에서 변수에 특정값을 대입한다거나,,,메쏘드를 호출한다거나,,,,이러한 기본적인 계산들을 원시작업이라고 합니다.
원시작업의 여러 특징
- 의사코드로 표현 가능
- 프로그래밍 언어와는 대체로 무관
- 정밀한 정의 중요 X
- 임의접근기계 모델에서 수행시 상수시간 소요
그리고 임의접근기계 모델이란
하나의 cpu를 가지고 무제한의 메모리를 가지는 추상적인 개념의 모델입니다.
이렇게해서 알고리즘상에서 원시작업의 수를 세면 특정한 '입력크기에 대한 함수'가 나오게 될것입니다.
이러한 실행시간 함수는 고유한 속성이 될 수 있습니다.
그리고 그런 실행시간을 간단하게 표현하는 BIG-O표현법이 있습니다.
Big-O를 통해서 함수 증가율의 상한을 나타낼 수 있습니다.
정확한 정의 : f(n)=O(g(n)) -> f(n)의 증가율은 g(n)의 증가율을 넘지 않는다.
빅오 구하기 ex) 2n + 10 = O(n) 3n^3 + 20n^2 + 5 = O(n^3)
빅오 크기 비교 : c < log n < log ^2 n < n < n log n < n^2 < n^3 < 2^n
