개인 공부용으로 정리하는 문서입니다.📖 실행시간
효율적인 알고리즘과 데이터구조는 1. 빠른 실행속도 와 2. 낮은 메모리 사용량 을 만족해야한다.
현대 프로그래밍에서는 용량에 대한 문제보다는 속도가 더욱 중요하다.
따라서 실행시간을 파악하여 어떤 데이터 구조와 알고리즘을 사용할지를 판단하는 것이 중요하다.📖 최악실행시간
실행속도를 구하는 방법에는 3가지가 있다.
1. 최악실행시간
2. 평균실행시간
3. 최선실행시간
이중 최선 실행시간은 별 의미가 없다.
운이 좋은 경우 빠르게 통과하는 것이 실행시간을 대표한다고 할 수 없다.
평균실행시간의 경우 또한 결정하기가 어렵다.
평균에 대한 정의가 어렵다.
인터넷 사용을 기준으로 들자면 어떤 검색어가 평균적인 검색어 인지를
파악하는 것은 매우 모호할 것이다.
그렇기에 최악실행시간을 사용하여 계산한다.📖 방법
최악실행시간을 구하는 방법은 2가지다.
1. 실험적 - 직접 돌려보기
2. 이론적 - 실행시간을 입력크기 n인 함수로 만들기
실험적은 공평한 비교가 불가하며 최악의 경우 무한정 커지는 반복을 세기가 힘들다.
실험때 모든 상황을 동일하게 설정해야하는데 CPU의 상태,전력 등 변수가 너무나 많다.
그래서 이론적 방법을 사용한다.
입력을 n으로 잡고 실행시간을 n에 관한 함수로 표현한다.📖 예시
int main(){
int arr[n];
for(int i=0;i<n;i++)
arr[i]=i;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
printf("%d ",arr[i]);
}
라는 문장이 있다고 해보자
선언은 딱한번이니 1
반복문은 n회
이중 반복은 n번씩 n번이니 n^2번 반복마다 실행하는 것은 출력1회느 그냥 n^2로 표현가능하다.
이를 다 더하면 시간복잡도는
n^2+n+1이라는 식으로 표현이 가능하다.📖 점근표기 Big-O
이때 n이 작을때는 실행시간에 큰 영향을 주지 못한다.
따라서 n이 무한대로 증가할때 시간복잡도를 알고자한다.
너무 디테일한 정보가 아닌 영향력 정도만 파악을 하려하며
이를 위해서 제일 큰 차수만을 남긴다.
위를 기준으로 하면 n^2만 남기는 것이다.
이를 표현하기 위해 O(n^2)로 표기한다.
이를 Big-O 표기법이라 한다.
학생