유미의 기록들

알고리즘 문제를 풀 때 예제 입출력이 맞게 나와도 실제 코드를 제출했을 때 시간초과로 통과하지 못하는 경우가 종종 있다. 우리가 작성한 코드의 실행 시간을 어떻게 알 수 있을까? 이러한 시간은 사용된 언어 종류, 컴퓨터 사양, 컴파일러 속도 등 여러가지 영향을 받게 된다. 따라서 시간복잡도를 설명할 때는 입력값과 연산 수행 시간의 상관관계를 중점으로 설명한다 시간복잡도 (time complexity) 입력크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간, 주요로직의 반복 횟수를 중점으로 측정됨 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 시간복잡도 표현방법은 3가지가 있다 1) 오메가 표기법 (Big-Ω) : 최상의 경우 2) 세타 표기법 (Big-θ) : 평균의 경우 3) 빅오 ..