시간 복잡도

시간 복잡도

@24.03.20

로그 시간 복잡도

💡

컴퓨터가 정보를 찾는데 걸리는 시간이 얼마나 빠른지를 나타내는 방법으로

수행 시간이 입력 크기에 비례하여 로그 함수의 증가율로 상승하기에 로그 시간이라 한다 .

• 시간 복잡도는 일반적으로 BIG O 표기법을 사용하여 표현
  • 알고리즘의 수행 시간이 입력 크기에 따라 얼마나 빠르게 증가하는지 표현
  • O : 차수 , log : 로그, n : 데이터의 개수를 뜻하며, 데이터의 개수가 많아져도 찾는데 필요한 시간이 많이 늘지는 않는다는 것을 의미
  • O(1) : 상수 시간 → 입력의 크기에 관계 없이 항상 일정한 시간이 소요
  • O(log n) : 로그 시간 → 입력한 크기에 비례하여 로그 함수의 증가율로 시간이 증가
  • O(n) : 선형 시간 → 입력한 크기에 비례하여 시간이 선형적으로 증가
  • O(n log n) : 선형 로그 시간 → 입력한 크기에 비례하여 로그 함수의 증가율로 시간이 증가하나, 로그 값에 비례하여 선형적으로 증가
  • O($n^2$) : 이차 시간 → 입력한 크기의 제곱에 비례하여 시간이 증가
  • O($2^n$) : 지수 시간 → 입력 크기에 비례하여 지수 함수의 증가율로 시간이 증가

• 빅 오메가 표기법: 최선의 경우의 시간 복잡도로, 최적의 상황에서 수행하는 시간의 하한

• 빅 세타 표기법 : 평균적인 경우의 시간 복잡도로, 알고리즘이 평균적으로 얼마나 빠르게 실행되는지를 나타냄

• 빅 오메가 역함수 표기법 : 최악의 경우의 시간 복잡도를 나타내는 대신, 알고리즘이 수행되는 시간에 대한 상한을 제공 즉 알고리즘의 실행 시간이 이 값보다 느릴 순 없다.