알고리즘 - 시간 복잡도

시간 복잡도

• 주어진 문제를 해결하기 위한 연산 횟수(실행 속도)

• 효율성 - 시간 : 연산양, 공간 : 메모리

• 일반적으로 1억번의 연산 = 1초

• 시간 복잡도 표기법
  - 빅-오메가 : 최선(best case)일때 연산 횟수

  • 빅-세타 : 보통(average case)일때 연산 횟수
  • 빅-오 : 최악(worst case)일때 연산 횟수

Q1. 빅-오 계산하기
크기가 n인 배열 arr 에 대해 다음 코드의 연삿 횟수를 빅-오 표기법으로 구하세요.

int total = 0;
for (int i=0; i<3; i++){
  for(int j=0; j<n; j++){
      total += arr[j];
    }
}

공간 복잡도

• 프로그램이 사용하는 메모리 크기
• 일반적으로 알고리즘 문제에서 메모리 크기 제한
  While문 → 무한루프 : 메모리 초과

배열

• 메모리 연속 공간에 값이 채워져 있는 형태의 자료구조
• 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있습니다.

int [] arr = new int[6];

• java.util.Arrays 클래스 (자료구조 x)
  • 배열을 다루는 다양한 메소드 포함
  • 모든 메소드는 클래스 메소드(static method)이므로, 객체 생성 없이 바로 사용
• 자주 사용하는 메소드
  • Arrays.toString()

구간 합

합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘

• 연속적인 인덱스의 합이 있을 시 사용

합 배열을 만드는 공식(배열A, 합 배열 S)
S[i] = S[i-1] + A[i]

투포인터

total < n → end 전진 (값 증가)
total == n → cnt++, start 전진
total > n → start 전진 (값 감소)

start와 end 이동 시 갱신(증가/감소)
👉 for문으로 구현 X