알고리즘 효율성

알고리즘 효율성 분석

• 시간 효율성
• 가장 중요한 평가 요소
• 실제 실행 시간을 측정할 수도 있지만, 대부분은 이론적으로 복잡도를 분석하는 방법을 사용함
• 공간 효율성
• 컴퓨터 메모리를 얼마나 사용하는지를 측정
• 알고리즘의 효율성 평가를 하려면 직접 구현하고, 동일한 조건의 하드웨어에서 동일한 OS, 소프트웨어를 사용하는 등의 조건이 많이 따른다
  따라서, 일반적으로 이론적으로 알고리즘의 복잡도를 분석하는 방법이 주로 사용된다.
• 알고리즘의 복잡도를 분석하기 위해 반드시 확인해야하는 사항들
• 알고리즘의 입력의 크기?
• 복잡도에 영향을 미치는 가장 핵심적인 기본 연산은 무엇인가?
• ex)다중 루프의 경우 가장 안쪽의 연산
• 입력의 크기가 증가함에 따라 처리시간은 어떤 형태로 증가하는가?
• 입력의 특성에 따라 알고리즘 효율성에는 어떤 차이가 있는가?

복잡도 함수와 증가 속도

• 기본 연산이 실행되는 전체 횟수는 입력의 개수 n에 영향을 받는데, 연산의 수를 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T(n)이라고 표기함
• 알고리즘의 효율성 분석은 충분히 큰 (n > n0) 입력에 대해서만 관심이 있음
• 입력의 크기가 무한대로 커짐에 따라 실행시간의 증가 속도(Order of growth)에만 관심이 있음
• 알고리즘을 구현하지 않고도 모든 입력에 대해 실행 하드웨어나 소프트웨어 환경과 관계없이 효율성 평가를 할 수 있음

최선,최악,평균적인 효율성

• 최선의 경우(Best case)
• 실행시간이 가장 적은 경우를 의미함
• 알고리즘 분석에서는 큰 의미가 없음
• 평균적인 경우(Average case)
• 알고리즘의 모든 입력을 고려하고 각 입력이 발생할 확률을 고려한 평균적인 실행시간을 의미함
• 모든 입력을 고려해야 하기때문에 정확히 계산하기가 어려움
• 최악의 경우(Worst case)
• 입력의 구성이 알고리즘의 실행시간을 가장 많이 요구하는 경우를 의미함
• 알고리즘에 가장 불리한 입력 데이터를 사용하는 최악의 경우에 대한 성능이 가장 중요하게 사용됨
• ex)자율주행 자동차나 항공 관제업무에 사용되는 알고리즘은 아무리 불리한 입력이 들어오더라도 일정한 시간안에 반드시 계산이 끝나야 사고 발생을 막을 수 있다