Time Complexity

• 알고리즘이 문제를 해결하는 데 걸리는 시간의 증가율을 나타내는 개념

Time Complexity(시간 복잡도)

• 알고리즘의 수행 시간을 분석하는 방법으로, 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타낸다.
• 시간 복잡도를 통해 주어진 알고리즘의 성능을 평가하고, 알고리즘 간의 효율성을 비교할 수 있다.

Big-O Complexity(Big-O 표기법)

• 시간 복잡도의 입력 크기에 대한 함수 표현으로 보통 Big-O 표기법을 사용하여 나타낸다.
• 최악(Big-O), 최선(Big-Ω), 평균(Big-θ)의 경우를 나타내는 세 가지 표기법이 있지만, 대부분의 경우 알고리즘의 최악의 실행 시간(Big-O)을 파악한다.

• 상수 시간(Constant time) - O(1)

  • 입력 크기에 관계없이 실행 시간이 일정한 알고리즘을 나타낸다.
  • ex) 배열의 첫 번째 요소에 접근

• 로그 시간(Logarithmic time) - O(log n)

  • 입력 크기에 비례하여 실행 시간이 log n에 비례하여 증가하는 알고리즘을 나타낸다.
  • ex) 이진 검색과 같이 입력을 반씩 분할하는 알고리즘

• 선형 시간(Linear time) - O(n)

  • 입력 크기에 비례하여 실행 시간이 선형으로 증가하는 알고리즘을 나타낸다.
  • ex) 리스트의 모든 요소를 확인하는 경우

• 선형 로그 시간(Linearithmic time) - O(n log n)

  • 입력 크기에 비례하여 실행 시간이 n log n에 비례하여 증가하는 알고리즘을 나타낸다.
  • ex) Merge Sort, Quick Sort

• 이차 시간(Quadratic time) - O(n^2)

  • 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘을 나타낸다.
  • ex) 중첩된 반복문이 있는 알고리즘

• 지수 시간(Exponential time) - O(2^n)

  • d입력 크기에 대해 2의 거듭제곱에 비례하여 실행 시간이 증가하는 알고리즘을 나타낸다.
  • ex) 완전 탐색과 같이 가능한 모든 조합을 시도하는 알고리즘

자료 구조에 따른 시간 복잡도

• 자료 구조에 따라 데이터를 삽입, 삭제, 탐색하는 데에 필요한 작업량이 다르기 때문에 시간 복잡도가 다르게 나타난다.