알고리즘 공부

알고리즘을 진행하면서 중요한 개념을 배웠습니다.

시간복잡도

알고리즘이 수행되는 시간의 효율성을 나타내는 개념

• 주로 입력 크기(input size)에 따라 알고리즘의 실행 시간이 어떻게 변하는지를 분석합니다. 시간복잡도는 빅오 표기법(Big-O Notation)을 사용하여 표현되며, 이는 최악의 경우(최대 시간 소요)를 가정한 측정 방법입니다.

시간복잡도 유형

• O(1) - 상수 시간(Constant Time):
  입력 크기에 상관없이 항상 일정한 시간이 소요되는 알고리즘.
  예: 배열의 특정 인덱스에 접근하는 작업.

• O(log n) - 로그 시간(Logarithmic Time):
  입력 크기가 커질수록 시간이 천천히 증가하는 알고리즘.
  예: 이진 탐색(Binary Search).

• O(n) - 선형 시간(Linear Time):
  입력 크기에 비례하여 시간이 증가하는 알고리즘.
  예: 배열의 모든 요소를 하나씩 순회하는 작업.

• O(n log n) - 로그 선형 시간(Log-Linear Time):
  입력 크기가 커질수록 선형적으로 증가하면서 로그 시간만큼 더해지는 알고리즘.
  예: 대부분의 효율적인 정렬 알고리즘(예: 퀵정렬, 병합정렬).

• O(n^2) - 이차 시간(Quadratic Time):
  입력 크기에 대한 제곱에 비례하여 시간이 증가하는 알고리즘.
  예: 버블 정렬, 선택 정렬.

• O(2^n) - 지수 시간(Exponential Time):
  입력 크기가 커질수록 시간이 지수적으로 증가하는 알고리즘.
  예: 피보나치 수열을 재귀적으로 계산하는 알고리즘(메모이제이션이나 다이나믹 프로그래밍을 사용하지 않는 경우).

• O(n!) - 팩토리얼 시간(Factorial Time):
  입력 크기가 커질수록 시간이 팩토리얼로 증가하는 알고리즘.
  예: 모든 가능한 순열을 생성하는 알고리즘.

빅오표기법

빅오 표기법은 주로 최악의 경우를 분석하지만, 때로는 평균 시간복잡도나 최선의 경우 시간복잡도도 분석합니다. 시간복잡도는 알고리즘의 효율성을 비교할 때 중요한 지표로 사용되며, 이를 통해 알고리즘이 큰 입력 데이터를 처리할 때 얼마나 효율적으로 동작하는지를 예측할 수 있습니다.

후기

디자인부터 시작해 CS지식이 부족합니다. 아주 기초적인 개념이라
정리하고 넘어가야 했고 나중에 시간을 더 투자하여 공부하면 좋을것 같습니다!