알고리즘의 성능과 시간복잡도

알고리즘의 성능

• 구현된 프로그램이 실행되는 동안 얼마나 많은 공간적 자원과 시간적 자원을 요구하는 가에 따라 결정
• 자원을 적게 요구하는 알고리즘이 성능이 더 좋다고 표현

공간적 자원

• 컴파일된 프로그램을 이루는 명령어 저장 공간: 하드디스크(HDD)
• 프로그램이 실행되는 동안 필요한 데이터 저장 공간: 메모리
• 프로그램의 제어 정보와 임시 정보 저장 공간

시간적 자원

• 알고리즘이 구현된 프로그램의 실행이 시작되어 종료될 때까지 걸리는 시간

알고리즘의 시간 복잡도

• 알고리즘의 시간적 성능을 분석하기 위해 입력크기 n에 대한 기본 연산의 실행 횟수를 함수 형태로 나타낸 것
• T(n) = n
• T(n) = n-1
• T(n) = n2
• T(n) =n(n-1)/2

알고리즘의 시간 복잡도 계산 예

• 숫자가 저장되어 있는 배열의 각 원소를 더해서 그 합을 출력해라
• 연산 횟수는 몇 번인가?

int sum = 0;
for(int i = 0; i < 10; i++){
    sum ++ A[i];
}

시간 복잡도 계산

• 배열의 크기 10개로 총 실행 횟수는 10회
• 배열의 크기가 n개라면 총 실행 횟수는 n회
  • 시간 복잡도: T(n) = n

알고리즘의 시간 복잡도 계산 예-2

• 연산 횟수 구하기 변경

int sum = 0;
for(int i = 0; i < 10; i++){
    sum += A[i];
    count++;
}

변경한 경우 시간 복잡도 계산

• 배열의 크기가 10개로 총 실행 횟수는 9회
• 배열의 크기가 n개라면 총 실행 횟수는 n-1회
• 시간 복잡도: T(n) = n - 1