devrabbit22 님의 블로그

알고리즘은 입력 크기가 아주 작으면 알고리즘의 효율성에 상관 없이 금방 끝난다. 알고리즘의 효율성이 문제가 되는 것은 입력의 크기가 충분히 클 때다. 그래서 알고리즘의 수행 시간은 항상 입력의 크기가 충분히 클 때 분석한다.즉, 점근적 분석을 한다.를 이용한 분석이 점근적 분석의 한 예시이다.변수의 크기가 충분히 큰 경우 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법이다. 이를 함수의 점근적 증가율이라고 하고, 그 표기법을 점근적 표기법이라 한다.고등학교에서 배우는 무한의 개념을 사용하면이다. 이것은 함수 >은 n이 충분히 커짐에 따라 2n+3의 비율로 증가한다는 뜻이다.점근적 표기법은 이를 좀 더 간명화한다. 이들 중 O-표기법을 사용하면이다.이것은 함수>은 n이 충분히 커짐에 따라 n에 대..

몇가지 기초 사항들알고리즘 분석의 필요성알고리즘을 설계하고나면 알고리즘이 자원을 얼마나 소모하는지 분석애햐 할 때가 많다. 자원이란 소요 시간이나 메모리, 통신대역 등이 될 수도 있지만 대부분은 소요 시간이 가장 중요한 관심 대상이 된다. 물론 다른 자원도 관심 대상이다. 메모리나 통신대역 등은 대부분 주어진 범위 내에서 문제가 되지 않지만 가끔 가장 중요한 대상이 되기도 한다.시간의 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적이다.시간 분석을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 필요한지 미리 짐작할 수 있다.ex) 디스크에 있는 3,000만 명의 고객 레코드를 한 시간 내에 생년월일 순으로 정렬하라는 요구를 받았을 떄, 사용하고자 하는 알고리즘의 소요 시간이 입력의 크..

알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것.알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다.설계하려는 알고리즘이 "무엇을"하는지 입력과 출력으로 명시할 수 있다.ex) 학생 100명의 시험 점소를 입력으로 받아 최고점을 출력하는 작업을 할 때 입출력 표현입력 : 100개의 점수출력 : 입력된 100개의 점수 중 최댓값입출력의 구체화된 표현입력 : 100개의 변수 x[1], ... x[100]의 값출력 : x[1], ..., x[100] 중 최댓값이 입출력을 요구하는 알고리즘의 대략 형태maxScore(x[], n){x[1...n]의 값을 차례대로 보면서 최댓값을 계산한다. //1return 찾은 최대값;}위에 작성한 서술적 표..