알고리즘 관련 개념 정리

최건우·2023년 2월 22일
0

알고리즘이란

  • 어떤 문제를 풀기 위한 절차나 방법.
  • 구체적으로는, 어떤 문제가 있을 때 주어진 '입력' 정보를 원하는 '출력' 정보로 만드는 일련의 과정을 구체적이고 명료하게 적은 것.
  • 문제를 푸는 방법은 꼭 한 가지만 있는 것은 아니다. 따라서 여러 가지 해답(알고리즘)을 만들고, '알고리즘 분석'을 통해 해당 문제에 가장 적합한 성능과 특징을 보이는 알고리즘을 선택해야 한다.

알고리즘의 계산 복잡도

입력 크기와 계산 횟수

  • 입력 크기와 계산 횟수는 알고리즘의 수행 성능에 영향을 미친다.
  • 대체로, 입력 크기가 작고 계산 횟수가 적을수록 수행 성능은 향상된다.
예시: 1부터 n까지의 합을 for 반복문으로 구할 때
- n은 입력 크기에 해당한다.
- 그런데, 프로그램은 덧셈을 1부터 n까지 n-1번 수행해야 하므로, 계산 횟수가 n에 정비례한다.

계산 복잡도의 표현: 대문자 O 표기법

  • 계산 복잡도(complexity): 어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도.
    - 대표적인 표기법: 'Big O' 표기법(=대문자 O 표기법)
  • 표기법
1. O(n): 필요한 계산 횟수가 입력 크기 n과 비례할 때
  - 필요한 계산 횟수가 입력 크기 n과 정비례하면, 모두 O(n)으로 표기한다.
  - 여기서 중요한 것은 '정비례' 하는 것이다. O(n)에서 n이 실제 계산 횟수를 의미하지 않음에 유의한다.
    - (ex) n의 크기에 따라 덧셈을 두 번씩 하는 알고리즘의 계산 복잡도 역시 O(n)이다. O(2n)이 아님에 유의한다.
2. O(1): 필요한 계산 횟수가 입력 크기 n과 무관할 때
  - 입력 크기가 커져도 계산 시간이 더 늘어나지 않는다면, 모두 O(1)로 표기한다.
  - O(1)에서 1이 실제로 계산 횟수가 1번임을 의미하지 않음에 유의한다.
    - (ex) 어떤 알고리즘이 입력 크기 n과 무관하게 사칙연산을 세 번 한다면, 이는 O(1)이다. O(3)이 아님에 유의한다.
  • 대체로, 입력 크기가 큰 문제를 풀 때는 복잡도가 O(1)인 알고리즘이 O(n)인 알고리즘보다 훨씬 더 빠른 경향이 있다.

계산 복잡도의 세부 항목

시간 복잡도

  • 시간 복잡도(time complexity): 어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석한 것.

공간 복잡도

  • 공간 복잡도(space complexity): 어떤 알고리즘을 수행하는 데 얼마나 많은 공간(ex. 메모리, 기억 장소)이 필요한지 분석한 것.




* 이 글은 '모두의 알고리즘 with 파이썬(이승찬, 2017)'을 개인적인 학습을 목적으로 요약한 게시글입니다. 문제가 있는 경우, 지적해 주시면 감사하겠습니다.

profile
부족한 경험을 채우기 위한 나만의 기록 공간

0개의 댓글